# Prime factors of LCM of array elements in Java

Finding the prime factors of each element in an array and combining them yields the prime factors of the components' least common multiple (LCM).

Example 1

Input: arr [] = {10, 15, 20}

Output: 2 3 5

Explanation: LCM of 10, 15, and 20 is 2 * 3 * 5 * 5 = 150. Prime factors are 2, 3, and 5.

Example 2

Input: arr [] = {12, 18, 24}

Output: 2 3

Explanation: LCM of 12, 18, and 24 is 2 * 2 * 2 * 3 * 3 = 72. Prime factors are 2 and 3.

Example 3

Input: arr [] = {25, 35, 45}

Output: 5 7

Explanation: LCM of 25, 35, and 45 is 5 * 5 * 7 * 3 = 525. Prime factors are 5 and 7.

## Approach 1: Using Prime Factorization

Prime Factorization is used to find the Least Common Multiple (LCM) of an array of numbers. It calculates the prime factors of each number in the array, then combines these factors to determine the LCM.

### Algorithm

Step 1: Define a function primeFactors that calculates the prime factors of a number without duplicates using trial division.

Step 2: Create a factorCount map to store the maximum power of each prime factor across all array elements.

Step 3: Iterate through the array, calculate prime factors for each element, and update factorCount accordingly.

Step 4: Compute the LCM by multiplying each prime factor to its maximum power in factorCount.

FileName: LCMPrimeFactorization.java

`import java.util.*;public class LCMPrimeFactorization {    // Function to calculate prime factors of a number without duplicates    public static List<Integer> primeFactors(int num) {        List<Integer> factors = new ArrayList<>();        // Divide the number by 2 as many times as possible        while (num % 2 == 0) {            factors.add(2); // Add 2 as a prime factor            num /= 2;        }        // Check for odd prime factors starting from 3 up to sqrt(num)        for (int i = 3; i <= Math.sqrt(num); i += 2) {            while (num % i == 0) {                factors.add(i); // Add the prime factor to the list                num /= i;            }        }        // If num is still greater than 2, it is a prime factor itself        if (num > 2) {            factors.add(num);        }        // Remove duplicates from the list of factors        Set<Integer> set = new HashSet<>(factors);        factors.clear();        factors.addAll(set);        return factors;    }    // Function to calculate LCM (Least Common Multiple) using prime factorization    public static int lcmUsingPrimeFactorization(int[] arr) {        Map<Integer, Integer> factorCount = new HashMap<>();        // Calculate prime factors for each element and update factorCount        for (int num : arr) {            List<Integer> factors = primeFactors(num);            for (int factor : factors) {                factorCount.put(factor, Math.max(factorCount.getOrDefault(factor, 0), 1));            }        }        int lcm = 1;        // Compute the LCM by multiplying each prime factor with its maximum power        for (Map.Entry<Integer, Integer> entry : factorCount.entrySet()) {            int factor = entry.getKey();            int count = entry.getValue();            lcm *= Math.pow(factor, count);        }        return lcm;    }    public static void main(String[] args) {        int[] arr = { 12, 18, 24 };        int lcmValue = lcmUsingPrimeFactorization(arr);        List<Integer> lcmFactors = primeFactors(lcmValue);        System.out.println("Prime factors of LCM: " + lcmFactors);    }}`

Output

`Prime factors of LCM: [2, 3]`

Time Complexity: The time complexity primarily depends on the prime factorization process, which typically runs in O(sqrt(N)) for each number N in the array. Therefore, the overall time complexity is O(N * sqrt(M)), where N is the number of elements in the array and M is the maximum value in the array.

Space Complexity: The space complexity is O(M) for storing the prime factors and their counts in factorCount, where M is the maximum value in the array.

## Approach 2: Using Formula

The Least Common Multiple (LCM) of an array of numbers using the LCM formula. It first computes the LCM using the formula LCM(a, b) = (a * b) / GCD(a, b), where GCD is the Greatest Common Divisor. Then, it finds the prime factors of the LCM.

### Algorithm

Step 1: Define a function gcd to calculate the Greatest Common Divisor (GCD) using the Euclidean algorithm.

Step 2: Define a function lcm to calculate the LCM of an array of numbers using the LCM formula and the gcd function.

Step 3: Define a function primeFactors to calculate the prime factors of a using trial division.

Step 4: Compute the LCM of the array elements using the lcm function and then find the prime factors of the LCM using the primeFactors function.

FileName: LCMUsingFormula.java

`import java.util.*;public class LCMUsingFormula {    // Function to calculate GCD (Greatest Common Divisor)    public static int gcd(int a, int b) {        if (b == 0) {            return a;        }        return gcd(b, a % b);    }    // Function to calculate LCM (Least Common Multiple) using the LCM formula    public static int lcm(int[] arr) {        int result = arr[0];        for (int i = 1; i < arr.length; i++) {            result = (result * arr[i]) / gcd(result, arr[i]);        }        return result;    }    // Function to calculate prime factors of a number without duplicates    public static List<Integer> primeFactors(int num) {        List<Integer> factors = new ArrayList<>();        while (num % 2 == 0) {            factors.add(2);            num /= 2;        }        for (int i = 3; i <= Math.sqrt(num); i += 2) {            while (num % i == 0) {                factors.add(i);                num /= i;            }        }        if (num > 2) {            factors.add(num);        }        // Remove duplicates from the list of factors        Set<Integer> set = new HashSet<>(factors);        factors.clear();        factors.addAll(set);        return factors;    }    public static void main(String[] args) {        int[] arr = { 12, 18, 24 };        int lcmValue = lcm(arr);        List<Integer> lcmFactors = primeFactors(lcmValue);        System.out.println("Prime factors of LCM: " + lcmFactors);    }}`

Output

`Prime factors of LCM: [2, 3]`

Time Complexity: The time complexity is O(N * log(M)), where M is the maximum value in the array. This is because calculating prime factors has and using the LCM formula.

Space Complexity: The space complexity is O(sqrt(M)) for storing the prime factors, where M is the maximum value in the array.