欧拉项目5在java中，为什么会有不同的结果

Question

/* 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这是错误的答案!!我知道还有很多更简单的算法，但我只是想知道我的问题在哪里……谁能告诉我这个问题?

Answer 1

计算时int溢出

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

得到360883904 / 20 = 18044195。

可以

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

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

Answer 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。