关于 arraylist java 中的 gcd

Question

输入2个整数例如 x=18 ,y=30 进行质因数分解并将每个质因数保存在数组列表中并在两个 arraylist

中找到 gcd 和 lcm

我试图找到 gcd，结果是 {2,3,3} 但我需要 {2,3} 所以我可以做 2*3

    public static int gcd(ArrayList<Integer> A,ArrayList<Integer> B)
    {
        int sum1=1;
        A.retainAll(B);
        
        for(int i=0;i<A.size();i++)
        {
            sum1*=A.get(i);
        }
        return sum1;
    }
    
    public static int lcm(ArrayList<Integer> A,ArrayList<Integer> B)
    {
        int sum = 1;
        for(int i=0;i<A.size();i++)
        {
            sum*=A.get(i);
            
        }
        for(int j=0;j<B.size();j++)
            {
                sum*=B.get(j);
                
            }
        return sum/gcd(A,B);
    }
    public static void main(String[] args) 
    {
        
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        int y = sc.nextInt();
        
        System.out.println(gcd(A(x),B(y)));
        System.out.println(lcm(A(x),B(y)));
        
    }
}

Answer 1

首先，因式分解方法A和B是相同的，所以只应保留和使用其中一种方法。

其次，为了使用质因数计算最大公约数，List::retainAll是不合适的，因为：

它没有正确处理重复条目。
它隐式修改列表 A。

可以借助每个因素的频率图计算出正确的交叉点：
对于 x = 18 和 A = [2, 3, 3] 以及 y = 30 和 B = [2, 3, 5]，交集是 [2, 3] -> gcd = 6:

public static int gcd(List<Integer> A, List<Integer> B) {
    Map<Integer, Integer> common = new HashMap<>();

    A.forEach(a -> common.merge(a, 1, Integer::sum));

    int gcd = 1;
    
    for (Integer b : B) {
        if (common.merge(b, -1, Integer::sum) >= 0) {
            gcd *= b;
        }
    }
    return gcd;
}

另外值得注意的是这里的列表A不受影响

所以为了测试：

int x = 18;
int y = 30;

ArrayList<Integer> A = A(x);
ArrayList<Integer> B = A(y);
System.out.println("gcd = " + gcd(A, B)); // gcd = 6
System.out.println("lcm = " + lcm(A, B)); // lcm = 90

关于 arraylist java 中的 gcd

about the gcd in arraylist java

java

arraylist