Dado un entero positivo n, encuentre el número de factores en n. donde n <= 10 5 .
Ejemplos:
Input : n = 3
Output : 4
Factors of 3! are 1, 2, 3, 6
Input : n = 4
Output : 8
Factors of 4! are 1, 2, 3, 4,
6, 8, 12, 24
Input : n = 16
Output : 5376
Tenga en cuenta que el enfoque de fuerza bruta ni siquiera funcionará aquí porque no podemos encontrar n! para un n tan grande Necesitaríamos un enfoque más realista para resolver este problema.
La idea se basa en la fórmula de Legendre .
Cualquier entero positivo se puede expresar como producto de potencias de sus factores primos. Supongamos un número n = p 1 a1 xp 2 a2 xp 3 a3 , …., p k ak donde p 1 , p 2 , p 3 , …., p k son primos distintos y a1, a2, a3,………… ..,ak son sus respectivos exponentes.
Entonces el número de divisores de n = (a1+1) x (a2+1) x (a3+1)…x (ak+1)
Así, no. de factores de n! ahora se puede calcular fácilmente encontrando primero los factores primos hasta n y luego calculando sus respectivos exponentes.
Los pasos principales de nuestro algoritmo son:
- Iterar de p = 1 a p = n y en cada iteración verificar si p es primo.
- Si p es primo entonces significa que es factor primo de n! ¡entonces encontramos el exponente de p en n! cual es
- Después de encontrar los respectivos exponentes de todos los factores primos, digamos que son a1, a2, a3, …., ak, ¡entonces los factores de n! = (a1+1) x (a2+1) x (a3+1)………………(ak+1)
Here is an illustration on how the algorithm works
for finding factors of 16!:
All prime less than 16 will be the prime factors of 16!.
so instead of finding all the prime factor of 16!.
we just need to find the primes less than 16 that will
automatically be the prime factors of 16!
Prime factors of 16! are: 2,3,5,7,11,13
Now to the exponent of 2 in 16!
= ⌊16/2⌋+ ⌊16/4⌋+ ⌊16/8⌋ + ⌊16/16⌋
= 8 + 4 + 2 + 1
= 15
Similarly,
exponent of 3 in 16! = ⌊16/3⌋ + ⌊16/9⌋ = 6
exponent of 5 in 16! = 3
exponent of 7 in 16! = 2
exponent of 11 in 16! = 1
exponent of 13 in 16! = 1
So, the no of factors of 16!
= (15+1) * (6+1) * (3+1) *(2+1)* (1+1) * (1+1)
= 5376
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to count number of factors of n
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
// Sieve of Eratosthenes to mark all prime number
// in array prime as 1
void sieve(int n, bool prime[])
{
// Initialize all numbers as prime
for (int i=1; i<=n; i++)
prime[i] = 1;
// Mark composites
prime[1] = 0;
for (int i=2; i*i<=n; i++)
{
if (prime[i])
{
for (int j=i*i; j<=n; j += i)
prime[j] = 0;
}
}
}
// Returns the highest exponent of p in n!
int expFactor(int n, int p)
{
int x = p;
int exponent = 0;
while ((n/x) > 0)
{
exponent += n/x;
x *= p;
}
return exponent;
}
// Returns the no of factors in n!
ll countFactors(int n)
{
// ans stores the no of factors in n!
ll ans = 1;
// Find all primes upto n
bool prime[n+1];
sieve(n, prime);
// Multiply exponent (of primes) added with 1
for (int p=1; p<=n; p++)
{
// if p is a prime then p is also a
// prime factor of n!
if (prime[p]==1)
ans *= (expFactor(n, p) + 1);
}
return ans;
}
// Driver code
int main()
{
int n = 16;
printf("Count of factors of %d! is %lld\n",
n, countFactors(n));
return 0;
}
Java
// Java program to count number of factors of n
import java.io.*;
class GFG {
// Sieve of Eratosthenes to mark all prime number
// in array prime as 1
static void sieve(int n, int prime[])
{
// Initialize all numbers as prime
for (int i = 1; i <= n; i++)
prime[i] = 1;
// Mark composites
prime[1] = 0;
for (int i = 2; i * i <= n; i++) {
if (prime[i] == 1) {
for (int j = i * i; j <= n; j += i)
prime[j] = 0;
}
}
}
// Returns the highest exponent of p in n!
static int expFactor(int n, int p)
{
int x = p;
int exponent = 0;
while ((n / x) > 0) {
exponent += n / x;
x *= p;
}
return exponent;
}
// Returns the no of factors in n!
static long countFactors(int n)
{
// ans stores the no of factors in n!
long ans = 1;
// Find all primes upto n
int prime[] = new int[n + 1];
sieve(n, prime);
// Multiply exponent (of primes) added with 1
for (int p = 1; p <= n; p++) {
// if p is a prime then p is also a
// prime factor of n!
if (prime[p] == 1)
ans *= (expFactor(n, p) + 1);
}
return ans;
}
// Driver code
public static void main(String args[])
{
int n = 16;
System.out.println("Count of factors of " +
n + " is " + countFactors(n));
}
}
// This code is contributed by Nikita Tiwari
Python 3
# python 3 program to count
# number of factors of n
# Returns the highest
# exponent of p in n!
def expFactor(n, p):
x = p
exponent = 0
while n // x > 0:
exponent += n // x
x *= p
return exponent
# Returns the no
# of factors in n!
def countFactors(n):
# ans stores the no
# of factors in n!
ans = 1
# Find all primes upto n
prime = [None]*(n+1)
# Initialize all
# numbers as prime
for i in range(1,n+1):
prime[i] = 1
# Mark composites
prime[1] = 0
i = 2
while i * i <= n:
if (prime[i]):
for j in range(i * i,n+1,i):
prime[j] = 0
i += 1
# Multiply exponent (of
# primes) added with 1
for p in range(1,n+1):
# if p is a prime then p
# is also a prime factor of n!
if (prime[p] == 1):
ans *= (expFactor(n, p) + 1)
return ans
# Driver Code
if __name__=='__main__':
n = 16
print("Count of factors of " + str(n) +
"! is " +str( countFactors(n)))
# This code is contributed by ChitraNayal
C#
// C# program to count number
// of factors of n
using System;
class GFG {
// Sieve of Eratosthenes to mark all
// prime number in array prime as 1
static void sieve(int n, int []prime)
{
// Initialize all numbers as prime
for (int i = 1; i <= n; i++)
prime[i] = 1;
// Mark composites
prime[1] = 0;
for (int i = 2; i * i <= n; i++)
{
if (prime[i] == 1)
{
for (int j = i * i; j <= n; j += i)
prime[j] = 0;
}
}
}
// Returns the highest exponent of p in n!
static int expFactor(int n, int p)
{
int x = p;
int exponent = 0;
while ((n / x) > 0)
{
exponent += n / x;
x *= p;
}
return exponent;
}
// Returns the no of factors in n!
static long countFactors(int n)
{
// ans stores the no of factors in n!
long ans = 1;
// Find all primes upto n
int []prime = new int[n + 1];
sieve(n, prime);
// Multiply exponent (of primes)
// added with 1
for (int p = 1; p <= n; p++)
{
// if p is a prime then p is
// also a prime factor of n!
if (prime[p] == 1)
ans *= (expFactor(n, p) + 1);
}
return ans;
}
// Driver code
public static void Main()
{
int n = 16;
Console.Write("Count of factors of " +
n + " is " + countFactors(n));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to count
// number of factors of n
// Returns the highest
// exponent of p in n!
function expFactor($n, $p)
{
$x = $p;
$exponent = 0;
while (intval($n / $x) > 0)
{
$exponent += intval($n / $x);
$x *= $p;
}
return $exponent;
}
// Returns the no
// of factors in n!
function countFactors($n)
{
// ans stores the no
// of factors in n!
$ans = 1;
// Find all primes upto n
$prime = array();
// Initialize all
// numbers as prime
for ($i = 1; $i <= $n; $i++)
$prime[$i] = 1;
// Mark composites
$prime[1] = 0;
for ($i = 2; $i * $i <= $n; $i++)
{
if ($prime[$i])
{
for ($j = $i * $i; $j <= $n; $j += $i)
$prime[$j] = 0;
}
}
// Multiply exponent (of
// primes) added with 1
for ($p = 1; $p <= $n; $p++)
{
// if p is a prime then p
// is also a prime factor of n!
if ($prime[$p] == 1)
$ans *= intval(expFactor($n, $p) + 1);
}
return $ans;
}
// Driver Code
$n = 16;
echo "Count of factors of " . $n .
"! is " . countFactors($n);
// This code is contributed by Sam007
?>
Javascript
<script>
// Javascript program to count number of factors of n
// Sieve of Eratosthenes to mark all prime number
// in array prime as 1
function sieve(n, prime)
{
// Initialize all numbers as prime
for (let i = 1; i <= n; i++)
prime[i] = 1;
// Mark composites
prime[1] = 0;
for (let i = 2; i * i <= n; i++)
{
if (prime[i] == 1)
{
for (let j = i * i; j <= n; j += i)
prime[j] = 0;
}
}
}
// Returns the highest exponent of p in n!
function expFactor(n,p)
{
let x = p;
let exponent = 0;
while ((n / x) > 0)
{
exponent += Math.floor(n / x);
x *= p;
}
return exponent;
}
// Returns the no of factors in n!
function countFactors(n)
{
// ans stores the no of factors in n!
let ans = 1;
// Find all primes upto n
let prime = new Array(n + 1);
for(let i = 0; i < n + 1; i++)
{
prime[i] = 0;
}
sieve(n, prime);
// Multiply exponent (of primes) added with 1
for (let p = 1; p <= n; p++)
{
// if p is a prime then p is also a
// prime factor of n!
if (prime[p] == 1)
ans *= (expFactor(n, p) + 1);
}
return ans;
}
// Driver code
let n = 16;
document.write("Count of factors of " +
n + "! is " + countFactors(n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción :
Count of factors of 16! is 5376
Nota: si la tarea es contar factores para múltiples valores de entrada, entonces podemos precalcular todos los números primos hasta el límite máximo 10 5 .
Este artículo es una contribución de Madhur Modi . 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