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

Stack Overflow用户

提问于 2019-09-12 16:58:16

回答 2查看 39关注 0票数 0

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

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);
    }           
}

java

回答 2

Stack Overflow用户

回答已采纳

发布于 2019-09-12 17:22:53

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

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

看看the euclidean algorithm吧。

票数 0

Stack Overflow用户

发布于 2019-09-12 17:26:48

正如Holloway所说。对于gcd，您可以使用：

public static long gcd(long P, long Q) {
        if (P % Q == 0) {
            return Q;
        } else {
            return gcd(Q, P % Q);
        }
    }

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/57903193

复制

相似问题

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

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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