我试图找到数字(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);
}
}
最佳答案
计算 gcd 的递归算法会导致堆栈溢出。运行相同的算法(在Python上快速测试),得到1-14的lcm为360360。要找到这个和15的gcd,会导致360360/15个递归调用(~24,000),这是Java无法处理的。
您需要找到一种非递归的方法来查找 gcd(或者至少是一种更有效的方法)。
关于java - 从 1 到 20 查找 lcm,给出错误 "at Main.gcd(Main.java:21)",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57903193/