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 6Entrada: 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>
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