Dado un entero n y un número primo p, encuentra el mayor x tal que p x (p elevado a x) ¡divide a n! (factorial)
Ejemplos:
Input: n = 7, p = 3 Output: x = 2 32 divides 7! and 2 is the largest such power of 3. Input: n = 10, p = 3 Output: x = 4 34 divides 10! and 4 is the largest such power of 3.
¡norte! es la multiplicación de {1, 2, 3, 4, …n}.
¿Cuántos números en {1, 2, 3, 4, ….. n} son divisibles por p?
Todo p’ésimo número es divisible por p en {1, 2, 3, 4, ….. n}. Por lo tanto en n!, hay ⌊n/p⌋ números divisibles por p. Entonces sabemos que el valor de x (¡la mayor potencia de p que divide a n!) es al menos ⌊n/p⌋.
¿Puede x ser mayor que ⌊n/p⌋?
Sí, puede haber números que sean divisibles por p 2 , p 3 , …
¿Cuántos números en {1, 2, 3, 4, ….. n} son divisibles por p 2 , p 3 , …?
Hay ⌊n/(p 2 )⌋ números divisibles por p 2 (Cada p 2 ‘ésimo número sería divisible). De manera similar, hay ⌊n/(p 3)⌋ números divisibles por p 3 y así sucesivamente.
¿Cuál es el mayor valor posible de x?
Entonces, la potencia más grande posible es ⌊n/p⌋ + ⌊n/(p 2 )⌋ + ⌊n/(p 3 )⌋ + ……
Tenga en cuenta que solo agregamos ⌊n/(p 2 )⌋ solo una vez (no dos veces ) ya que una p ya está considerada por la expresión ⌊n/p⌋. De manera similar, consideramos ⌊n/(p 3 )⌋ (no tres veces).
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find largest x such that p*x divides n!
#include <iostream>
using namespace std;
// Returns largest power of p that divides n!
int largestPower(int n, int p)
{
// Initialize result
int x = 0;
// Calculate x = n/p + n/(p^2) + n/(p^3) + ....
while (n)
{
n /= p;
x += n;
}
return x;
}
// Driver code
int main()
{
int n = 10, p = 3;
cout << "The largest power of "<< p <<
" that divides " << n << "! is "<<
largestPower(n, p) << endl;
return 0;
}
// This code is contributed by shubhamsingh10
C
// C program to find largest x such that p*x divides n!
#include <stdio.h>
// Returns largest power of p that divides n!
int largestPower(int n, int p)
{
// Initialize result
int x = 0;
// Calculate x = n/p + n/(p^2) + n/(p^3) + ....
while (n)
{
n /= p;
x += n;
}
return x;
}
// Driver program
int main()
{
int n = 10, p = 3;
printf("The largest power of %d that divides %d! is %d\n",
p, n, largestPower(n, p));
return 0;
}
Java
// Java program to find largest x such that p*x divides n!
import java.io.*;
class GFG
{
// Function that returns largest power of p
// that divides n!
static int Largestpower(int n, int p)
{
// Initialize result
int ans = 0;
// Calculate x = n/p + n/(p^2) + n/(p^3) + ....
while (n > 0)
{
n /= p;
ans += n;
}
return ans;
}
// Driver program
public static void main (String[] args)
{
int n = 10;
int p = 3;
System.out.println(" The largest power of " + p + " that divides "
+ n + "! is " + Largestpower(n, p));
}
}
Python3
# Python3 program to find largest
# x such that p*x divides n!
# Returns largest power of p that divides n!
def largestPower(n, p):
# Initialize result
x = 0
# Calculate x = n/p + n/(p^2) + n/(p^3) + ....
while n:
n /= p
x += n
return x
# Driver program
n = 10; p = 3
print ("The largest power of %d that divides %d! is %d\n"%
(p, n, largestPower(n, p)))
# This code is contributed by Shreyanshi Arun.
C#
// C# program to find largest x
// such that p * x divides n!
using System;
public class GFG
{
// Function that returns largest
// power of p that divides n!
static int Largestpower(int n, int p)
{
// Initialize result
int ans = 0;
// Calculate x = n / p + n / (p ^ 2) +
// n / (p ^ 3) + ....
while (n > 0)
{
n /= p;
ans += n;
}
return ans;
}
// Driver Code
public static void Main ()
{
int n = 10;
int p = 3;
Console.Write(" The largest power of " + p + " that divides "
+ n + "! is " + Largestpower(n, p));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find largest
// x such that p*x divides n!
// Returns largest power
// of p that divides n!
function largestPower($n, $p)
{
// Initialize result
$x = 0;
// Calculate x = n/p +
// n/(p^2) + n/(p^3) + ....
while ($n)
{
$n = (int)$n / $p;
$x += $n;
}
return floor($x);
}
// Driver Code
$n = 10;
$p = 3;
echo "The largest power of ", $p ;
echo " that divides ",$n , "! is ";
echo largestPower($n, $p);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find largest
// x such that p*x divides n!
// Returns largest power
// of p that divides n!
function largestPower(n, p)
{
// Initialize result
let x = 0;
// Calculate x = n/p +
// n/(p^2) + n/(p^3) + ....
while (n)
{
n = parseInt(n / p);
x += n;
}
return Math.floor(x);
}
// Driver Code
let n = 10;
let p = 3;
document.write("The largest power of " + p);
document.write(" that divides " + n + "! is ");
document.write(largestPower(n, p));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
The largest power of 3 that divides 10! is 4
Complejidad del tiempo: O(log p n)
Espacio Auxiliar: O(1)
¿Qué hacer si p no es primo?
Podemos encontrar todos los factores primos de p y calcular el resultado de cada factor primo. Consulte ¡La mayor potencia de k en n! (factorial) donde k puede no ser primo para los detalles.
Fuente:
http://e-maxx.ru/algo/factorial_divisors
Este artículo es una contribución de Ankur . 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