Given a number n, the task is to write an efficient program to print all unique prime factors of n.
Example
Input: 12
Output: 2, 3
Explanation: All prime factors or 12 are 2, 2, 3. In those factors, unique factors
are 2 and 3.
Input: 315
Output: 3, 5, 7
Steps to find all prime factors
1) While n is divisible by 2, print 2 and divide n by 2.
2) After step 1, n must be odd. Now start a loop from i = 3 to the square root of n. While i divides n, print i and divide n by i, increment i by 2 and continue.
3) If n is a prime number and is greater than 2, then n will not become 1 by the above two steps. So print n if it is greater than 2.
In the second step, the loop runs to the square root of n because the pairs for the product of nth number only possible when one number is less than greater than the square root of n and the second number is greater and equal to the square root of n.
For example, let n =16 square root of 16 is 4 and the factors of 16 are 1×16, 16×1, 2×8, 8×2, 4×4 in this sequence the first number should be less than or equal to the square root of n and the second number is greater than and equal to square root to n.
Mathematically proof :
- Let x < sqrt(n) and y < sqrt(n) multiply both equation x×y < n hence when any x and y less than n. The product of any x and y is always less than n.
- Let x > sqrt(n) and y > sqrt(n) multiply both equations x×y > n hence when any x and y less than n.The product of any x and y is always less than n.
- Let one number is below sqrt(n) and the second number above sqrt(n). In this case there is always at least one pair of numbers whose product is n. let x and y be the two numbers whose product is n. We can write x = sqrt(n) * sqrt(n)/y ⇾ equation 1st
There are two conditions :
- When y < sqrt(n) i.e 1 < sqrt(n)/y so we can write 1st equation x = sqrt(n)*(1+b) hence x > sqrt(n)
- When y < sqrt(n) i.e 1 > sqrt(n)/y so we can write 1st equation x = sqrt(n)*(1-b) hence x < sqrt(n).
Hence, we can conclude the for x*y=n at least one number is less than equal to sqrt(n) or greater than and equal to sqrt(n)
This concept is used in many Number theory Algorithms like a sieve, Finding all divisors of n, etc
Approaches For Finding unique prime Factors of given Number
1. Approach using HashSet
- While n is divisible by 2, store 2 in the set and divide n by 2.
- After the above step, n must be odd. Now start a loop from i = 3 to the square root of n. While i divides n, store i in the set and divide n by i. After i fails to divide n, increment i by 2 and continue.
- If n is a prime number and is greater than 2, then n will not become 1 by the above two steps. So store in set n if it is greater than 2.
Java
// Java Program to print all unique prime factorsimport java.io.*;import java.lang.Math;import java.util.*;class GFG { // A function to print all prime factors // of a given number n public static void primeFactors(int n, HashSet<Integer> h) { // Print the number of 2s that divide n while (n % 2 == 0) { h.add(2); 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 += 2) { // While i divides n, print i and divide n while (n % i == 0) { h.add(i); n /= i; } } // This condition is to handle the case when // n is a prime number greater than 2 if (n > 2) h.add(n); } static void printFactors(HashSet<Integer> H) { // Iterator over the HashSet Iterator<Integer> It = H.iterator(); // printing the elements of HashSet while (It.hasNext()) { System.out.print(It.next() + " "); } System.out.println(); } public static void main(String[] args) { int n = 15; HashSet<Integer> h = new HashSet<>(); primeFactors(n, h); // print the unique factors printFactors(h); }} |
3 5
Time Complexity: O(sqrt(n))
Space Complexity : O(sqrt(n))
2. Approach Using Sieve :
- Marks all the multiples of numbers till sqrt(n) reason mention above where n is the maximum length of the array.
- The array looks like for multiple of 2 and so on till length of the array.
| 0 | 1 | 2 | 3 | 2 |
|---|
- Mark all the remaining multiples of all number till sqrt(n). For finding the factors of an nth number.
Java
// Java Program to print all unique prime factorsimport java.util.*;import java.io.*;public class GFG { static int dp[] = new int[100001]; static void fill() { int n = 100000; for (int i = 1; i <= n; ++i) { dp[i] = i; } // mark the multiply of 2 for (int i = 2; i <= n; i += 2) { dp[i] = 2; } // mark the multiple of less than sqrt(n) for (int i = 3; i <= Math.sqrt(n); ++i) { for (int j = i * i; j <= n; j += i) { if (dp[j] == j) { dp[j] = i; } } } } static void Factors(int n, HashSet<Integer> h) { // when n is prime number if (dp[n] == n) { h.add(n); return; } else { while (dp[n] != n) { // Adding the multiple. h.add(dp[n]); n = n / dp[n]; } h.add(n); return; } } static void print(HashSet<Integer> h) { Iterator<Integer> it = h.iterator(); // printing the elements while (it.hasNext()) { System.out.print(it.next() + " "); } } public static void main(String[] args) { int n = 21; fill(); HashSet<Integer> h = new HashSet<>(); // finding the factors Factors(n, h); print(h); }} |
3 7
Time Complexity: O(logn)
space complexity : O(n)
