Java中数组中所有数字的最小公倍数

Question

我有一个int数组，想要找到该数组中所有值的最小公倍数（LCM）。我已经单独编写了一个lcm方法，它需要两个值作为输入，并返回它们的LCM值。我的lcm方法完全正常，但是当我使用它来查找所有值的LCM时，我得到了错误的答案。

这里是我的gcd和lcm方法：

public static int gcd(int a, int b){
    if (a<b) return gcd(b,a);
    if (a%b==0) return b;
    else return gcd(a, a%b);
}


public static int lcm(int a, int b){
    return ((a*b)/gcd(a,b));

} 

这是我对数组值的最小公倍数的计算结果：

public static int lcmofarray(int[] arr, int start, int end){
    if ((end-start)==1) return lcm(arr[start],arr[end-1]);
    else return (lcm (arr[start], lcmofarray(arr, start+1, end)));
}

当我输入一个包含数字1到5的数组 arr，0为start，数组长度为end时，我得到30作为答案，但我想要60。当我输入一个包含从1到10所有数字的数组时，我得到840而不是2520。我真的无法解释这个问题。

算法应该是可以工作的-我已经在我的脑海中计算过了。无法弄清楚代码的问题所在。

任何帮助将不胜感激。

- Anindya Guha

---

我不确定我是否理解你的设置方式，但似乎你的第一个if语句会在同一个数字上调用LCM函数。例如，如果start = 0，end = 1，则你将返回lcm(arr [0]，arr [0]) = arr [0]。 - Kon

我猜我可以使用循环，但此时我想知道我的代码为什么不起作用。 @Kon 我希望基本情况是：当数组中剩下两个元素时，找到这两个元素的最小公倍数。（输入数组永远不会少于两个元素。）我应该将其更改为（end-start==2）吗？ - Anindya Guha

你的代码对我来说似乎是有效的。你能提供一下你实现的 lcm 吗？ - johnchen902

例如，如果您的数组长度为2，则其最大索引为 end = 2。然后您正在询问 start - end == 1，但您从0开始，2-0！=1，因此它不认为数组中有2个元素。修复它的一种方法是将 == 1 更改为 == 2。那是一种方式。使用循环会更明智。 - Kon

问题现在很清楚：else return gcd(b, a%b); - johnchen902

Answer 1

如果您更改gcd函数为：

public static int gcd(int a, int b){
    if (a<b) return gcd(b,a);
    if (a%b==0) return b;
    else return gcd(b, a%b);
}

它应该可以正常工作。

- user2514440

Answer 2

这是一个编程程序，使用公式 lcmgcd=ab 来寻找 n 个数字数组的最小公倍数和最大公因数。

public class Main
{
    public static void main(String[] args) {
        int a[]={63,105,210};
        int lcm=1,fir=lcm,res=0;
        for(int i=0;i<a.length;i++)
        {
            int sec=a[i];
            lcm=(fir*sec)/gcd(fir,sec);
            fir=lcm;
        }
        for(int j=0;j<a.length;j++)
        {
            res=gcd(res,a[j]);
        }
        System.out.println("lcm is "+lcm+" "+"gcd is "+res);
    }
    
    public static int gcd(int a,int b)
    {
        if(b==0)
        {
            return a;
        }
        return gcd(b,a%b);
    }
}

- Dinesh Kumar

Answer 3

上述方法看起来不错，但由于递归调用而导致堆栈溢出错误：

请查看以下解决方案：

    public int findHCF(int a, int b) {

    if (b>a){
        return findHCF(b, a);
    }

    while(a%b!=0){

        int temp = b;
        b=a%b;
        a=temp;
    }
    return b;
}

- Akanksha

---

我相信你也在进行递归调用。你能否强调一下，你的代码有何不同？ - Ravi

不，我没有进行递归调用。我正在使用迭代方法。只有第一条语句 if(a<b) findGCD(b,a) ，它只执行一次，而且只有当 a<b 时才执行。其余所有内容都是迭代的。 - Akanksha

我明白了。但是，我不理解交换a和b值的逻辑。顺便说一句，它会给出错误的输出。https://ideone.com/aLKxuL - Ravi

是的，我已经检查过了。交换a和b并不是必需的。但是它每次都能给我正确的输出。你能否请提供一个输出不正确的用例？另外，如果你有更好的解决方案或者修改我的方案，请随意添加。谢谢。 - Akanksha

我在上一条评论中分享了一个链接。你的代码输出错误。如果我更改你的代码，那么答案将完全改变 :-) - Ravi

嗨，Ravi，谢谢！我找到了错误。稍后会修复它。我得走了。 - Akanksha

Answer 4

代码背后的逻辑简要说明- LCM(a,b)=a*b/HCF(a,b)

您可以使用以下代码实现此操作-

package hackerrank;

/*
 * Author Hirak JD
 */
import java.util.Arrays;

public class LCM {
    public static void main(String args[]) {
        int[] set= {2,3,6,8};
        int lcm=1;
        for(int each:set) {
            lcm=calculateLcm(lcm,each);
        }

        System.out.println("LCM for "+Arrays.toString(set)+" is : "+lcm);

    }

    private static int calculateLcm(int lcm, int each) {
        return lcm*each/gcd(lcm,each);
    }

    private static int gcd(int val1, int val2) {
        if(val1==0||val2==0)
            return 0;

        if(val1==val2)
            return val1;

        if(val1>val2)
            return gcd(val1-val2,val2);
        return gcd(val1,val2-val1);
    }
}

- Hirak JD