2 
/* Smallest multiple */
/*
 * 2520 is the smallest number that can be divided by each
 *  of the numbers from 1 to 10 without any remainder.What 
 *  is the smallest positive number that is evenly divisible 
 *  by all of the numbers from 1 to 20?
 */
public class SmallestMultiple {
    public static int gcd(int m, int n){
        if(n>m){
            int temp = m;
            m = n;
            n = temp;
        }
        int gcdNum = m;
        while(m != 0){
            m = gcdNum%n;
            gcdNum = n;
            n = m;
        }
        return gcdNum;
    }
    private static int lcm(int m, int n){
        return m*n/gcd(m,n);
    }
    static int multiple(int start, int end){
        if(start > end){
            int temp = end;
            end = start;
            start = temp;
        }
        else if(start == end)
            return start;
        else
            return lcm(end, multiple(start, end-1));
        return multiple(start, end);
    }
    public static void main(String[] args) {
        System.out.println(multiple(11,19)); // line a--Which is equal to multiple(1,19) 
        System.out.println(multiple(11,20)); // line b--Which is equal to multiple(1,20)
    }
}

我认为multiple(1,19) 和multiple(1,20) 的答案会得到相同的结果。但是使用我的代码，它们是不同的，multiple(1,19)=232792560（正确答案）和multiple(1,20)=18044195这是错误答案！！！我知道有很多更简单的算法，但我只想知道我的问题在哪里......谁能告诉我问题？

4

2 回答 2

3

计算时int溢出

Prelude> 232792560 * 20
4655851200
Prelude> it `quotRem` (2^32)
(1,360883904)

从而获得360883904 / 20 = 18044195.

你可以

  • 使用long或
  • 计算m * (n/gcd(n,m))

避免溢出（第二种方法不会让你走得更远，如果上限是 23，int太小而无法容纳结果）。

于 2013-04-18T15:02:46.003 回答
2

您的问题几乎只是整数溢出。

Java 中最大的int数字是Integer.MAX_VALUE = 2147483647.

在某些时候，您尝试运行lcm( 20, 232792560 ). 后者是 的结果multiplay(1,19)。

在您的函数内部，您尝试计算m*n/gcd(m,n).

随着m == 20,n == 18044195和gcd(m,n) == 20, 这得到20 * 18044195 / 20.

第一个产品实际上是20 * 18044195 == 4655851200，它大于Integer.MAX_VALUE，因此会发生溢出并且您的总结果运行不佳。

一种解决方案是在任何地方切换到一种long类型，其最大值为Long.MAX_VALUE == 9223372036854775807.

于 2013-04-18T15:04:45.037 回答