about the gcd in arraylist java

Question

input 2 integers eg x=18 ,y=30 do prime factorization and save each prime factor in arraylist and find gcd and lcm in two arraylist

i tried to find gcd,it result {2,3,3} but i need {2,3} so i can do the 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

First, the factorization methods A and B are identical, so only one of these methods should be kept and used.

Second, in order to calculate the greatest common divisor using the prime factors, List::retainAll is not appropriate because:

1. it does not handle duplicate entries properly.
2. it modifies list A implicitly.

A proper intersection can be computed with the help of a frequency map for each factor:
for x = 18 and A = [2, 3, 3] and y = 30 and B = [2, 3, 5] the intersection is [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;
}

It is also worth to note that here list A is not affected.

So for the test:

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