Dado un número n, necesitamos calcular la suma de los divisores del factorial del número.
Ejemplos:
Input : 4 Output : 60 Factorial of 4 is 24. Divisors of 24 are 1 2 3 4 6 8 12 24, sum of these is 60. Input : 6 Output : 2418
Una solución simple es primero calcular el factorial del número dado, luego contar los divisores numéricos del factorial. Esta solución no es eficiente y puede causar desbordamiento debido al cálculo factorial.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find sum of proper divisor of // factorial of a number #include <bits/stdc++.h> using namespace std; // function to calculate factorial int fact(int n) { if (n == 0) return 1; return n * fact(n - 1); } // function to calculate sum of divisor int div(int x) { int ans = 0; for (int i = 1; i<= x; i++) if (x % i == 0) ans += i; return ans; } // Returns sum of divisors of n! int sumFactDiv(int n) { return div(fact(n)); } // Driver Code int main() { int n = 4; cout << sumFactDiv(n); } // This code is contributed // by Akanksha Rai
C
// C program to find sum of proper divisor of // factorial of a number #include <stdio.h> // function to calculate factorial int fact(int n) { if (n == 0) return 1; return n * fact(n - 1); } // function to calculate sum of divisor int div(int x) { int ans = 0; for (int i = 1; i<= x; i++) if (x % i == 0) ans += i; return ans; } // Returns sum of divisors of n! int sumFactDiv(int n) { return div(fact(n)); } // driver program int main() { int n = 4; printf("%d",sumFactDiv(n)); }
Java
// Java program to find sum of proper divisor of // factorial of a number import java.io.*; import java.util.*; public class Division { // function to calculate factorial static int fact(int n) { if (n == 0) return 1; return n*fact(n-1); } // function to calculate sum of divisor static int div(int x) { int ans = 0; for (int i = 1; i<= x; i++) if (x%i == 0) ans += i; return ans; } // Returns sum of divisors of n! static int sumFactDiv(int n) { return div(fact(n)); } // driver program public static void main(String args[]) { int n = 4; System.out.println(sumFactDiv(n)); } }
Python3
# Python 3 program to find sum of proper # divisor of factorial of a number # function to calculate factorial def fact(n): if (n == 0): return 1 return n * fact(n - 1) # function to calculate sum # of divisor def div(x): ans = 0; for i in range(1, x + 1): if (x % i == 0): ans += i return ans # Returns sum of divisors of n! def sumFactDiv(n): return div(fact(n)) # Driver Code n = 4 print(sumFactDiv(n)) # This code is contributed # by Rajput-Ji
C#
// C# program to find sum of proper // divisor of factorial of a number using System; class Division { // function to calculate factorial static int fac(int n) { if (n == 0) return 1; return n * fac(n - 1); } // function to calculate // sum of divisor static int div(int x) { int ans = 0; for (int i = 1; i <= x; i++) if (x % i == 0) ans += i; return ans; } // Returns sum of divisors of n! static int sumFactDiv(int n) { return div(fac(n)); } // Driver Code public static void Main() { int n = 4; Console.Write(sumFactDiv(n)); } } // This code is contributed by Nitin Mittal.
PHP
<?php // PHP program to find sum of proper // divisor of factorial of a number // function to calculate factorial function fact($n) { if ($n == 0) return 1; return $n * fact($n - 1); } // function to calculate sum of divisor function div($x) { $ans = 0; for ($i = 1; $i<= $x; $i++) if ($x % $i == 0) $ans += $i; return $ans; } // Returns sum of divisors of n! function sumFactDiv($n) { return div(fact($n)); } // Driver Code $n = 4; echo sumFactDiv($n); // This code is contributed // by Akanksha Rai ?>
Javascript
<script> // JavaScript program to find // sum of proper divisor of // factorial of a number // function to calculate factorial function fact(n) { if (n == 0) return 1; return n * fact(n - 1); } // function to calculate sum of divisor function div(x) { let ans = 0; for (let i = 1; i<= x; i++) if (x % i == 0) ans += i; return ans; } // Returns sum of divisors of n! function sumFactDiv(n) { return div(fact(n)); } // Driver Code let n = 4; document.write(sumFactDiv(n)); // This code is contributed by Surbhi Tyagi. </script>
Producción :
60
Una solución eficiente se basa en la fórmula de Legendre . A continuación se muestran los pasos.
- Encuentre todos los números primos menores o iguales a n (número de entrada). Podemos usar el algoritmo Sieve para esto. Sea n 6. Todos los números primos menores que 6 son {2, 3, 5}.
- Para cada número primo, p encuentra la mayor potencia que divide a n!. Usamos la fórmula de Legendre para este propósito.
- ¡La mayor potencia de 2 que divide a 6!, exp1 = 4.
- ¡La mayor potencia de 3 que divide a 6!, exp2 = 2.
- La mayor potencia de 5 que divide a 6!, exp3 = 1.
- El resultado se basa en la Función Divisor .
C++
// C++ program to find sum of divisors in n! #include<bits/stdc++.h> #include<math.h> using namespace std; // allPrimes[] stores all prime numbers less // than or equal to n. vector<int> allPrimes; // Fills above vector allPrimes[] for a given n void sieve(int n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // not a prime, else true. vector<bool> prime(n+1, true); // Loop to update prime[] for (int p = 2; p*p <= n; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p*2; i <= n; i += p) prime[i] = false; } } // Store primes in the vector allPrimes for (int p = 2; p <= n; p++) if (prime[p]) allPrimes.push_back(p); } // Function to find all result of factorial number int factorialDivisors(int n) { sieve(n); // create sieve // Initialize result int result = 1; // find exponents of all primes which divides n // and less than n for (int i = 0; i < allPrimes.size(); i++) { // Current divisor int p = allPrimes[i]; // Find the highest power (stored in exp)' // of allPrimes[i] that divides n using // Legendre's formula. int exp = 0; while (p <= n) { exp = exp + (n/p); p = p*allPrimes[i]; } // Using the divisor function to calculate // the sum result = result*(pow(allPrimes[i], exp+1)-1)/ (allPrimes[i]-1); } // return total divisors return result; } // Driver program to run the cases int main() { cout << factorialDivisors(4); return 0; }
Java
// Java program to find sum of divisors in n! import java.util.*; class GFG{ // allPrimes[] stores all prime numbers less // than or equal to n. static ArrayList<Integer> allPrimes=new ArrayList<Integer>(); // Fills above vector allPrimes[] for a given n static void sieve(int n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // not a prime, else true. boolean[] prime=new boolean[n+1]; // Loop to update prime[] for (int p = 2; p*p <= n; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p] == false) { // Update all multiples of p for (int i = p*2; i <= n; i += p) prime[i] = true; } } // Store primes in the vector allPrimes for (int p = 2; p <= n; p++) if (prime[p]==false) allPrimes.add(p); } // Function to find all result of factorial number static int factorialDivisors(int n) { sieve(n); // create sieve // Initialize result int result = 1; // find exponents of all primes which divides n // and less than n for (int i = 0; i < allPrimes.size(); i++) { // Current divisor int p = allPrimes.get(i); // Find the highest power (stored in exp)' // of allPrimes[i] that divides n using // Legendre's formula. int exp = 0; while (p <= n) { exp = exp + (n/p); p = p*allPrimes.get(i); } // Using the divisor function to calculate // the sum result = result*((int)Math.pow(allPrimes.get(i), exp+1)-1)/ (allPrimes.get(i)-1); } // return total divisors return result; } // Driver program to run the cases public static void main(String[] args) { System.out.println(factorialDivisors(4)); } } // This code is contributed by mits
Python3
# Python3 program to find sum of divisors in n! # allPrimes[] stores all prime numbers # less than or equal to n. allPrimes = []; # Fills above vector allPrimes[] # for a given n def sieve(n): # Create a boolean array "prime[0..n]" # and initialize all entries it as true. # A value in prime[i] will finally be # false if i is not a prime, else true. prime = [True] * (n + 1); # Loop to update prime[] p = 2; while (p * p <= n): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p for i in range(p * 2, n + 1, p): prime[i] = False; p += 1; # Store primes in the vector allPrimes for p in range(2, n + 1): if (prime[p]): allPrimes.append(p); # Function to find all result of factorial number def factorialDivisors(n): sieve(n); # create sieve # Initialize result result = 1; # find exponents of all primes which # divides n and less than n for i in range(len(allPrimes)): # Current divisor p = allPrimes[i]; # Find the highest power (stored in exp)' # of allPrimes[i] that divides n using # Legendre's formula. exp = 0; while (p <= n): exp = exp + int(n / p); p = p * allPrimes[i]; # Using the divisor function to # calculate the sum result = int(result * (pow(allPrimes[i], exp + 1) - 1) / (allPrimes[i] - 1)); # return total divisors return result; # Driver Code print(factorialDivisors(4)); # This code is contributed by mits
C#
// C# program to find sum of divisors in n! using System; using System.Collections; class GFG{ // allPrimes[] stores all prime numbers less // than or equal to n. static ArrayList allPrimes=new ArrayList(); // Fills above vector allPrimes[] for a given n static void sieve(int n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // not a prime, else true. bool[] prime=new bool[n+1]; // Loop to update prime[] for (int p = 2; p*p <= n; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p] == false) { // Update all multiples of p for (int i = p*2; i <= n; i += p) prime[i] = true; } } // Store primes in the vector allPrimes for (int p = 2; p <= n; p++) if (prime[p]==false) allPrimes.Add(p); } // Function to find all result of factorial number static int factorialDivisors(int n) { sieve(n); // create sieve // Initialize result int result = 1; // find exponents of all primes which divides n // and less than n for (int i = 0; i < allPrimes.Count; i++) { // Current divisor int p = (int)allPrimes[i]; // Find the highest power (stored in exp)' // of allPrimes[i] that divides n using // Legendre's formula. int exp = 0; while (p <= n) { exp = exp + (n/p); p = p*(int)allPrimes[i]; } // Using the divisor function to calculate // the sum result = result*((int)Math.Pow((int)allPrimes[i], exp+1)-1)/ ((int)allPrimes[i]-1); } // return total divisors return result; } // Driver program to run the cases static void Main() { Console.WriteLine(factorialDivisors(4)); } } // This code is contributed by mits
PHP
<?php // PHP program to find sum of divisors in n! // allPrimes[] stores all prime numbers less // than or equal to n. $allPrimes=array(); // Fills above vector allPrimes[] for a given n function sieve($n) { global $allPrimes; // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // not a prime, else true. $prime=array_fill(0,$n+1,true); // Loop to update prime[] for ($p = 2; $p*$p <= $n; $p++) { // If prime[p] is not changed, then it // is a prime if ($prime[$p] == true) { // Update all multiples of p for ($i = $p*2; $i <= $n; $i += $p) $prime[$i] = false; } } // Store primes in the vector allPrimes for ($p = 2; $p <= $n; $p++) if ($prime[$p]) array_push($allPrimes,$p); } // Function to find all result of factorial number function factorialDivisors($n) { global $allPrimes; sieve($n); // create sieve // Initialize result $result = 1; // find exponents of all primes which divides n // and less than n for ($i = 0; $i < count($allPrimes); $i++) { // Current divisor $p = $allPrimes[$i]; // Find the highest power (stored in exp)' // of allPrimes[i] that divides n using // Legendre's formula. $exp = 0; while ($p <= $n) { $exp = $exp + (int)($n/$p); $p = $p*$allPrimes[$i]; } // Using the divisor function to calculate // the sum $result = $result*(pow($allPrimes[$i], $exp+1)-1)/ ($allPrimes[$i]-1); } // return total divisors return $result; } // Driver program to run the cases print(factorialDivisors(4)); // This code is contributed by mits ?>
Javascript
<script> // Javascript program to find sum of divisors in n! // allPrimes[] stores all prime numbers less // than or equal to n. let allPrimes=[]; // Fills above vector allPrimes[] for a given n function sieve(n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // not a prime, else true. let prime = new Array(n + 1); for(let i = 0; i < n + 1; i++) prime[i] = true; // Loop to update prime[] for(let p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p] == true) { // Update all multiples of p for(let i = p * 2; i <= n; i += p) prime[i] = false; } } // Store primes in the vector allPrimes for(let p = 2; p <= n; p++) if (prime[p]) allPrimes.push(p); } // Function to find all result of // factorial number function factorialDivisors( n) { // Create sieve sieve(n); // Initialize result let result = 1; // Find exponents of all primes which // divides n and less than n for(let i = 0; i < allPrimes.length; i++) { // Current divisor let p = allPrimes[i]; // Find the highest power (stored in exp)' // of allPrimes[i] that divides n using // Legendre's formula. let exp = 0; while (p <= n) { exp = exp + Math.floor(n/p); p = p*allPrimes[i]; } // Using the divisor function to calculate // the sum result = Math.floor(result * (Math.pow( allPrimes[i], exp + 1) - 1) / (allPrimes[i] - 1)); } // Return total divisors return result; } // Driver code document.write(factorialDivisors(4)); // This code is contributed by rag2127 </script>
Producción:
60
Este artículo es una contribución de Pramod Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA