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