Generar todos los divisores de un número usando su descomposición en factores primos

Dado un número entero N , la tarea es encontrar todos sus divisores usando su descomposición en factores primos.

Ejemplos: 

Entrada: N = 6 
Salida: 1 2 3 6

Entrada: N = 10 
Salida: 1 2 5 10

Enfoque: Como todo número mayor que 1 se puede representar en su descomposición en factores primos como p 1 a 1 *p 2 a 2 *……*p k a k , donde p i es un número primo, k ≥ 1 y a i es un entero positivo. 
Ahora todos los posibles divisores pueden generarse recursivamente si se conoce el recuento de ocurrencias de cada factor primo de n. Para cada factor primo p i , se puede incluir x veces donde 0 ≤ x ≤ a i . Primero, encuentre la descomposición en factores primos de n usando este enfoque y, para cada factor primo, guárdelo con el conteo de su ocurrencia.
A continuación se muestra la implementación del enfoque anterior:

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 occurenceand 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 occurenceand 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 occurenceand 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 occurenceand 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 occurenceand 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>
Producción: 

1 3 2 6

 

Publicación traducida automáticamente

Artículo escrito por BhupendraYadav y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *