Given an integer N, the task is to find all of its divisors using its prime factorization.
Examples:
Input: N = 6
Output: 1 2 3 6Input: N = 10
Output: 1 2 5 10
Approach: As every number greater than 1 can be represented in its prime factorization as p1a1*p2a2*……*pkak, where pi is a prime number, k ? 1 and ai is a positive integer.
Now all the possible divisors can be generated recursively if the count of occurrence of every prime factor of n is known. For every prime factor pi, it can be included x times where 0 ? x ? ai. First, find the prime factorization of n using this approach and for every prime factor, store it with the count of its occurrence.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include "iostream"#include "vector"using namespace std;struct primeFactorization { // to store the prime factor // and its highest power int countOfPf, primeFactor;};// Recursive function to generate all the// divisors from the prime factorsvoid generateDivisors(int curIndex, int curDivisor, vector<primeFactorization>& arr){ // Base case i.e. we do not have more // primeFactors to include if (curIndex == arr.size()) { cout << curDivisor << ' '; return; } for (int i = 0; i <= arr[curIndex].countOfPf; ++i) { generateDivisors(curIndex + 1, curDivisor, arr); curDivisor *= arr[curIndex].primeFactor; }}// Function to find the divisors of nvoid findDivisors(int n){ // To store the prime factors along // with their highest power vector<primeFactorization> arr; // Finding prime factorization of n for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { int count = 0; while (n % i == 0) { n /= i; count += 1; } // For every prime factor we are storing // count of it's occurrenceand itself. arr.push_back({ count, i }); } } // If n is prime if (n > 1) { arr.push_back({ 1, n }); } int curIndex = 0, curDivisor = 1; // Generate all the divisors generateDivisors(curIndex, curDivisor, arr);}// Driver codeint main(){ int n = 6; findDivisors(n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {static class primeFactorization { // to store the prime factor // and its highest power int countOfPf, primeFactor; public primeFactorization(int countOfPf, int primeFactor) { this.countOfPf = countOfPf; this.primeFactor = primeFactor; }}// Recursive function to generate all the// divisors from the prime factorsstatic void generateDivisors(int curIndex, int curDivisor, Vector<primeFactorization> arr){ // Base case i.e. we do not have more // primeFactors to include if (curIndex == arr.size()) { System.out.print(curDivisor + " "); return; } for (int i = 0; i <= arr.get(curIndex).countOfPf; ++i) { generateDivisors(curIndex + 1, curDivisor, arr); curDivisor *= arr.get(curIndex).primeFactor; }}// Function to find the divisors of nstatic void findDivisors(int n){ // To store the prime factors along // with their highest power Vector<primeFactorization> arr = new Vector<>(); // Finding prime factorization of n for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { int count = 0; while (n % i == 0) { n /= i; count += 1; } // For every prime factor we are storing // count of it's occurrenceand itself. arr.add(new primeFactorization(count, i )); } } // If n is prime if (n > 1) { arr.add(new primeFactorization( 1, n )); } int curIndex = 0, curDivisor = 1; // Generate all the divisors generateDivisors(curIndex, curDivisor, arr);}// Driver codepublic static void main(String []args) { int n = 6; findDivisors(n);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Recursive function to generate all the # divisors from the prime factors def generateDivisors(curIndex, curDivisor, arr): # Base case i.e. we do not have more # primeFactors to include if (curIndex == len(arr)): print(curDivisor, end = ' ') return for i in range(arr[curIndex][0] + 1): generateDivisors(curIndex + 1, curDivisor, arr) curDivisor *= arr[curIndex][1] # Function to find the divisors of n def findDivisors(n): # To store the prime factors along # with their highest power arr = [] # Finding prime factorization of n i = 2 while(i * i <= n): if (n % i == 0): count = 0 while (n % i == 0): n //= i count += 1 # For every prime factor we are storing # count of it's occurrenceand itself. arr.append([count, i]) # If n is prime if (n > 1): arr.append([1, n]) curIndex = 0 curDivisor = 1 # Generate all the divisors generateDivisors(curIndex, curDivisor, arr) # Driver code n = 6findDivisors(n) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# implementation of the approachusing System; using System.Collections.Generic;class GFG {public class primeFactorization { // to store the prime factor // and its highest power public int countOfPf, primeFactor; public primeFactorization(int countOfPf, int primeFactor) { this.countOfPf = countOfPf; this.primeFactor = primeFactor; }}// Recursive function to generate all the// divisors from the prime factorsstatic void generateDivisors(int curIndex, int curDivisor, List<primeFactorization> arr){ // Base case i.e. we do not have more // primeFactors to include if (curIndex == arr.Count) { Console.Write(curDivisor + " "); return; } for (int i = 0; i <= arr[curIndex].countOfPf; ++i) { generateDivisors(curIndex + 1, curDivisor, arr); curDivisor *= arr[curIndex].primeFactor; }}// Function to find the divisors of nstatic void findDivisors(int n){ // To store the prime factors along // with their highest power List<primeFactorization> arr = new List<primeFactorization>(); // Finding prime factorization of n for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { int count = 0; while (n % i == 0) { n /= i; count += 1; } // For every prime factor we are storing // count of it's occurrenceand itself. arr.Add(new primeFactorization(count, i )); } } // If n is prime if (n > 1) { arr.Add(new primeFactorization( 1, n )); } int curIndex = 0, curDivisor = 1; // Generate all the divisors generateDivisors(curIndex, curDivisor, arr);}// Driver codepublic static void Main(String []args) { int n = 6; findDivisors(n);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript implementation of the approach// Recursive function to generate all the// divisors from the prime factorsfunction generateDivisors(curIndex, curDivisor, arr){ // Base case i.e. we do not have more // primeFactors to include if (curIndex == arr.length) { document.write(curDivisor + " "); return; } for (var i = 0; i <= arr[curIndex][0]; ++i) { generateDivisors(curIndex + 1, curDivisor, arr); curDivisor *= arr[curIndex][1]; }}// Function to find the divisors of nfunction findDivisors(n){ // To store the prime factors along // with their highest power arr = []; // Finding prime factorization of n for (var i = 2; i * i <= n; ++i) { if (n % i == 0) { var count = 0; while (n % i == 0) { n /= i; count += 1; } // For every prime factor we are storing // count of it's occurrenceand itself. arr.push([ count, i ]); } } // If n is prime if (n > 1) { arr.push([ 1, n ]); } var curIndex = 0, curDivisor = 1; // Generate all the divisors generateDivisors(curIndex, curDivisor, arr);}// driver codevar n = 6;findDivisors(n);// This code contributed by shubhamsingh10</script> |
Output:
1 3 2 6
Time Complexity: O(sqrt(n))
Auxiliary Space: O(sqrt(n))
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!
