Dado un número n , ¡cuenta el número total de divisores de n! .
Ejemplos:
Entrada: n = 4
Salida: 8
Explicación:
4! es 24. Los divisores de 24 son 1, 2, 3, 4, 6,
8, 12 y 24.Entrada: n = 5
Salida: 16
Explicación:
5! es 120. Los divisores de 120 son 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24 30, 40, 60 y 12
Una solución simple es primero calcular el factorial del número dado, luego contar el número de divisores del factorial. Esta solución no es eficiente y puede causar desbordamiento debido al cálculo factorial.
Una mejor solución 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.
El valor de la mayor potencia que divide a n! es ⌊n/p⌋ + ⌊n/(p 2 )⌋ + ⌊n/(p 3 )⌋ + ……
Sean estos valores exp1, exp2, exp3,… Usando la fórmula anterior, obtenemos los siguientes valores para n = 6.- ¡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 es (exp1 + 1) * (exp2 + 1) * (exp3 + 1)… para todos los números primos, Para n = 6, los valores exp1, exp2 y exp3 son 4 2 y 1 respectivamente (calculados en el paso anterior 2). Entonces nuestro resultado es (4 + 1)*(2 + 1) * (1 + 1) = 30
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find count of divisors in n!
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
// allPrimes[] stores all prime numbers less
// than or equal to n.
vector<ull> 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
ull factorialDivisors(ull n)
{
sieve(n); // create sieve
// Initialize result
ull result = 1;
// find exponents of all primes which divides n
// and less than n
for (int i=0; i < allPrimes.size(); i++)
{
// Current divisor
ull p = allPrimes[i];
// Find the highest power (stored in exp)'
// of allPrimes[i] that divides n using
// Legendre's formula.
ull exp = 0;
while (p <= n)
{
exp = exp + (n/p);
p = p*allPrimes[i];
}
// Multiply exponents of all primes less
// than n
result = result*(exp+1);
}
// return total divisors
return result;
}
// Driver code
int main()
{
cout << factorialDivisors(6);
return 0;
}
Java
// JAVA program to find count of divisors in n!
import java.util.*;
class GFG
{
// allPrimes[] stores all prime numbers less
// than or equal to n.
static Vector<Integer> allPrimes=new Vector<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];
for(int i=0;i<=n;i++)
prime[i]=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.add(p);
}
// Function to find all result of factorial number
static long factorialDivisors(int n)
{
sieve(n); // create sieve
// Initialize result
long result = 1;
// find exponents of all primes which divides n
// and less than n
for (int i=0; i < allPrimes.size(); i++)
{
// Current divisor
long p = allPrimes.get(i);
// Find the highest power (stored in exp)'
// of allPrimes[i] that divides n using
// Legendre's formula.
long exp = 0;
while (p <= n)
{
exp = exp + (n/p);
p = p*allPrimes.get(i);
}
// Multiply exponents of all primes less
// than n
result = result*(exp+1);
}
// return total divisors
return result;
}
// Driver code
public static void main(String []args)
{
System.out.println(factorialDivisors(6));
}
}
//This code is contributed by ihritik
Python3
# Python3 program to find count # 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 i = p * 2; while(i <= n): prime[i] = False; i += p; 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]; # Multiply exponents of all # primes less than n result = result * (exp + 1); # return total divisors return result; # Driver Code print(factorialDivisors(6)); # This code is contributed by mits
C#
// C# program to find count 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];
for(int i = 0; i <= n; i++)
prime[i] = 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.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];
}
// Multiply exponents of all primes less
// than n
result = result * (exp + 1);
}
// return total divisors
return result;
}
// Driver code
public static void Main()
{
Console.WriteLine(factorialDivisors(6));
}
}
//This code is contributed by chandan_jnu
PHP
<?php
// PHP program to find count 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];
}
// Multiply exponents of all primes
// less than n
$result = $result * ($exp + 1);
}
// return total divisors
return $result;
}
// Driver Code
echo factorialDivisors(6);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript program to find count 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; 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)
{
sieve(n); // create sieve
// 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 + parseInt(n / p, 10);
p = p * allPrimes[i];
}
// Multiply exponents of all primes less
// than n
result = result * (exp + 1);
}
// return total divisors
return result;
}
document.write(factorialDivisors(6));
</script>
Producción
30
Este artículo es una contribución de Shashank Mishra (Gullu) . Este artículo está revisado por el equipo GeeksforGeeks.
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