Generating all divisors of a number using its prime factorization

0 0 5 minutes read

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 6

Input: N = 10
Output: 1 2 5 10

Approach: As every number greater than 1 can be represented in its prime factorization as p₁^a_¹*p₂^a_²*……*p_k^a_^k, where p_i is a prime number, k ? 1 and a_i 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 p_i, it can be included x times where 0 ? x ? a_i. 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 factors
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()) {
        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 n
void 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 code
int main()
{
    int n = 6;
 
    findDivisors(n);
 
    return 0;
}

Java

// Java implementation of the approach
import 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 factors
static 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 n
static 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 code
public 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 = 6
findDivisors(n) 
 
# This code is contributed by SHUBHAMSINGH10

C#

// C# implementation of the approach
using 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 factors
static 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 n
static 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 code
public 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 factors
function 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 n
function 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 code
var 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 zambiatek!