java - 从 1 到 20 查找 lcm，给出错误 "at Main.gcd(Main.java:21)"

Question

我试图找到数字(1,2,3,4....20)的lcm，这是一个非常简单的java程序，但它给了我一个错误。这个错误只在我运行循环到 20 时出现，但当我运行到 10 时才出现。答案是 232792560，这是一个 9 位数字，应该很容易出现长数据类型，所以我怀疑它是溢出问题。我找不到错误，请帮忙。

static long gcd(long a, long b)
{
    if(a==b) return a;

    if(a>b)
    {
        return gcd(a-b , b);
    }
    else{
        return gcd(a, b-a);
    }
}

static long lcm(long a, long b)
{
    return (a*b)/gcd(a, b);
}   

public static void main(String[] args) {

    long l=1;
    for(long i=1;i<=20;i++)
    {
        l=lcm(l , i);
        System.out.println(l);
    }           
}

Answer 1

计算 gcd 的递归算法会导致堆栈溢出。运行相同的算法(在Python上快速测试)，得到1-14的lcm为360360。要找到这个和15的gcd，会导致360360/15个递归调用(~24,000)，这是Java无法处理的。

您需要找到一种非递归的方法来查找 gcd(或者至少是一种更有效的方法)。

看看the euclidean algorithm .