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 ListprimeFactors(int num) { List 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 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 factorCount = new HashMap<>(); // Calculate prime factors for each element and update factorCount for (int num : arr) { List 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 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 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 ListprimeFactors(int num) { List 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 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 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.