Java Program to find Product of unique prime factors of a number
Given a number n, we need to find the product of all of its unique prime factors. Prime factors: It is basically a factor of the number that is a prime number itself.
Examples:
Input: num = 10 Output: Product is 10 Explanation: Here, the input number is 10 having only 2 prime factors and they are 5 and 2. And hence their product is 10. Input : num = 25 Output: Product is 5 Explanation: Here, for the input to be 25 we have only one unique prime factor i.e 5. And hence the required product is 5.
Method 1 (Simple)
Using a loop from i = 2 to n and check if i is a factor of n then check if i is prime number itself if yes then store product in product variable and continue this process till i = n.
// Java program to find product of // unique prime factors of a number. public class GFG { public static long productPrimeFactors( int n) { long product = 1 ; for ( int i = 2 ; i <= n; i++) { // Checking if 'i' is factor of num if (n % i == 0 ) { // Checking if 'i' is a Prime number boolean isPrime = true ; for ( int j = 2 ; j <= i / 2 ; j++) { if (i % j == 0 ) { isPrime = false ; break ; } } // condition if 'i' is Prime number // as well as factor of num if (isPrime) { product = product * i; } } } return product; } public static void main(String[] args) { int n = 44 ; System.out.print(productPrimeFactors(n)); } } // Contributed by _omg |
Output:
22
Method 2 (Efficient)
The idea is based on Efficient program to print all prime factors of a given number
// Java program to find product of // unique prime factors of a number. import java.util.*; import java.lang.*; public class GFG { public static long productPrimeFactors( int n) { long product = 1 ; // Handle prime factor 2 explicitly so that // can optimally handle other prime factors. if (n % 2 == 0 ) { product *= 2 ; while (n % 2 == 0 ) n = n / 2 ; } // n must be odd at this point. So we can // skip one element (Note i = i +2) for ( int i = 3 ; i <= Math.sqrt(n); i = i + 2 ) { // While i divides n, print i and // divide n if (n % i == 0 ) { product = product * i; while (n % i == 0 ) n = n / i; } } // This condition is to handle the case when n // is a prime number greater than 2 if (n > 2 ) product = product * n; return product; } public static void main(String[] args) { int n = 44 ; System.out.print(productPrimeFactors(n)); } } // Contributed by _omg |
Output:
22
Please refer complete article on Product of unique prime factors of a number for more details!
Contact Us