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