Given a number N, the task is to find the distinct Prime Factors of N.
Examples:
Input: N = 12
Output: 2 3
Explanation: The factors of 12 are 1, 2, 3, 4, 6, 12.
Among these the distinct prime factors are 2 and 3.Input: N = 39
Output: 3 13
Approach: The approach is to use a map to check whether a given factor of the number has occurred earlier or not. Now follow the below steps to solve this problem:
- Create a map visited to keep track of all previous prime factors.
- Create a variable C, and initialize it with 2.
- While N is divisible by C, print C if C is not present in the map. Now divide N by C. Also increment C by 1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find distinct prime factor// of a number Nvoid distinctPrimeFactors(int N){ if (N < 2) { cout << -1; } int c = 2; unordered_map<int, bool> visited; while (N > 1) { if (N % c == 0) { if (!visited) { cout << c << " "; visited = 1; } N /= c; } else c++; }}// Driver Codeint main(){ int N = 39; distinctPrimeFactors(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG{ // Function to find distinct prime factor // of a number N static void distinctPrimeFactors(int N) { if (N < 2) { System.out.print(-1); } int c = 2; // Create a new dictionary of // strings, with string keys. HashMap<Integer, Boolean> visited = new HashMap<>(); for(int i = 0; i < N; i++) { visited.put(i, false); } while (N > 1) { if (N % c == 0) { if(visited.containsKey(c)){ if (!visited.get(c)) { System.out.print(c + " "); visited.put(c, true); } } N /= c; } else c++; } } // Driver Code public static void main(String[] args) { int N = 39; distinctPrimeFactors(N); }}// This code is contributed by Samim Hossain Mondal |
Python3
# python3 program for the above approach# Function to find distinct prime factor# of a number Ndef distinctPrimeFactors(N): if (N < 2): print(-1) c = 2 visited = {} while (N > 1): if (N % c == 0): if (not c in visited): print(c, end=" ") visited = 1 if c in visited else 0 N //= c else: c += 1# Driver Codeif __name__ == "__main__": N = 39 distinctPrimeFactors(N)# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find distinct prime factor // of a number N static void distinctPrimeFactors(int N) { if (N < 2) { Console.Write(-1); } int c = 2; // Create a new dictionary of // strings, with string keys. Dictionary<int, bool> visited = new Dictionary<int, bool>(); for(int i = 0; i < N; i++) { visited[i] = false; } while (N > 1) { if (N % c == 0) { if(visited.ContainsKey(c)){ if (!visited) { Console.Write(c + " "); visited = true; } } N /= c; } else c++; } } // Driver Code public static void Main() { int N = 39; distinctPrimeFactors(N); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for the above approach // Function to find distinct prime factor // of a number N const distinctPrimeFactors = (N) => { if (N < 2) { document.write(-1); } let c = 2; let visited = {}; while (N > 1) { if (N % c == 0) { if (!(c in visited)) { document.write(`${c} `); visited = 1; } N = parseInt(N / c); } else c++; } } // Driver Code let N = 39; distinctPrimeFactors(N);// This code is contributed by rakeshsahni</script> |
Output
3 13
Time Complexity: O(N)
Auxiliary Space: O(N1/2)
Efficient Approach: This approach is similar to above approach where we find prime factors. The only difference is that we traverse from 2 to sqrt(n) to find all prime factors since we know that is sufficient for checking for prime numbers as well. If the number is still found to be greater than 2 then it is prime and we need to print it as well.
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find distinct prime factor// of a number Nvoid distinctPrimeFactors(int N){ if (N < 2) { cout << -1; return; } if (N == 2) { cout << 2; return; } unordered_map<int, bool> visited; for (int i = 2; i * i <= N; i++) { while (N % i == 0) { if (!visited[i]) { cout << i << " "; visited[i] = 1; } N /= i; } } if (N > 2) cout << N;}// Driver Codeint main(){ int N = 315; distinctPrimeFactors(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find distinct prime factor // of a number N static void distinctPrimeFactors(int N) { if (N < 2) { System.out.print(-1); return; } if (N == 2) { System.out.print(2); return; } HashMap<Integer, Boolean> visited = new HashMap<>(); for (int i = 2; i * i <= N; i++) { while (N % i == 0) { if (!visited.containsKey(i)) { System.out.print(i + " "); visited.put(i, true); } N /= i; } } if (N > 2) { System.out.print(N); } } // Driver Code public static void main(String[] args) { int N = 315; distinctPrimeFactors(N); }}// This code is contributed by Taranpreet |
Python3
# Python program for the above approach# Function to find distinct prime factor# of a number Ndef distinctPrimeFactors(N): if (N < 2): print(-1) return if N == 2: print(2) return visited = {} i = 2 while(i * i <= N): while(N % i == 0): if(i not in visited): print(i , end = " ") visited[i] = 1 N //= i i+=1 if(N > 2): print(N)# Driver CodeN = 315distinctPrimeFactors(N);# This code is contributed by Shubham Singh |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find distinct prime factor // of a number N static void distinctPrimeFactors(int N) { if (N < 2) { Console.Write(-1); return; } if (N == 2) { Console.Write(2); return; } Dictionary<int, bool> visited = new Dictionary<int, bool>(); for (int i = 2; i * i <= N; i++) { while (N % i == 0) { if (!visited.ContainsKey(i)) { Console.Write(i + " "); visited[i] = true; } N /= i; } } if (N > 2) { Console.Write(N); } } // Driver code public static void Main() { int N = 315; distinctPrimeFactors(N); }}// This code is contributed by avijitmondal1998 |
Javascript
<script>// Javascript program for the above approach// Function to find distinct prime factor// of a number Nfunction distinctPrimeFactors(N){ if (N < 2) { document.write(-1); return; } if (N === 2) { document.write(2); return; } visited = {}; for(var i = 2; i * i <= N; i++) { while(N % i == 0) { if(!visited[i]) { document.write(i + " "); visited[i] = 1; } N /= i; } } if(N > 2) document.write(N);}// Driver Codevar N = 315;distinctPrimeFactors(N);// This code is contributed by Shubham Singh</script> |
Output
3 5 7
Time Complexity: O(N^(1/2))
Auxiliary Space: O(N^(1/2))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
