¡Potencia de un número primo ‘r’ en n!

Dado un entero n, encuentre la potencia de un número primo dado (r) en n.
Ejemplos: 
 

Input  : n = 6  r = 3
         Factorial of 6 is 720 = 2^4 * 3^2 *5 (prime factor 2,3,5)
         and power of 3 is 2 
Output : 2

Input  : n = 2000 r = 7
Output : 330

Un método simple es calcular primero el factorial de n y luego factorizarlo para encontrar la potencia de un número primo. 
El método anterior puede causar un desbordamiento de números un poco más grandes, ya que el factorial de un número es un número grande. La idea es considerar factores primos de un factorial n.
Legendre Factorización de n!  
Para cualquier número primo p y cualquier entero n, sea Vp(n) el exponente de la mayor potencia de p que divide a n (es decir, la valoración p-ádica de n). Entonces 
Vp(n) = sumatoria de piso(n / p^i) e i va de 1 a infinito 
Mientras que la fórmula del lado derecho es una suma infinita, para cualquier valor particular de n y p tiene solo un número finito de términos distintos de cero : para cada i lo suficientemente grande como para que p^i > n, uno tiene floor(n/p^i) = 0 . ya que, la suma es convergente.
 

Power of ‘r’ in n! = floor(n/r) + floor(n/r^2) + floor(n/r^3) + ....

Programa para contar potencias de un no. r en n! basado en la fórmula anterior. 
 

// C++ program to find power of
// a prime number ‘r’ in n!
#include <bits/stdc++.h>
using  namespace std;
 
// Function to return power of a
// no. 'r' in factorial of n
int power(int n, int r)
{          
    // Keep dividing n by powers of
    // 'r' and update count
    int count = 0;
    for (int i = r; (n / i) >= 1; i = i * r)   
        count += n / i;
    return count;
}
 
// Driver program to
// test above function
int main()
{
    int n = 6,  r = 3;  
    printf(" %d ", power(n, r));   
    return 0;
}

// Java program to find power of
// a prime number 'r' in n!
 
class GFG {
     
// Function to return power of a
// no. 'r' in factorial of n
static int power(int n, int r) {
     
    // Keep dividing n by powers of
    // 'r' and update count
    int count = 0;
    for (int i = r; (n / i) >= 1; i = i * r)
    count += n / i;
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 6, r = 3;
    System.out.print(power(n, r));
}
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to find power
# of a prime number ‘r’ in n!
 
# Function to return power of a
# no. 'r' in factorial of n
def power(n, r):
         
    # Keep dividing n by powers of
    # 'r' and update count
    count = 0; i = r
     
    while((n / i) >= 1):
        count += n / i
        i = i * r
         
    return int(count)
 
# Driver Code
n = 6; r = 3
print(power(n, r))
 
# This code is contributed by Smitha Dinesh Semwal.

// C# program to find power of
// a prime number 'r' in n!
using System;
 
class GFG {
     
// Function to return power of a
// no. 'r' in factorial of n
static int power(int n, int r) {
     
    // Keep dividing n by powers of
    // 'r' and update count
    int count = 0;
    for (int i = r; (n / i) >= 1; i = i * r)
    count += n / i;
    return count;
}
 
// Driver code
public static void Main()
{
    int n = 6, r = 3;
    Console.WriteLine(power(n, r));
}
}
 
// This code is contributed by vt_m.

<?php
//PHP program to find power of
// a prime number ‘r’ in n!
 
// Function to return power of a
// no. 'r' in factorial of n
function power($n, $r)
{        
     
    // Keep dividing n by powers 
    // of 'r' and update count
    $count = 0;
    for ($i = $r; ($n / $i) >= 1;
                   $i = $i * $r)
        $count += $n / $i;
    return $count;
}
 
    // Driver Code
    $n = 6; $r = 3;
    echo power($n, $r);
 
// This code is contributed by ajit
?>

<script>
 
// JavaScript program to find power of
// a prime number 'r' in n!
 
// Function to return power of a
// no. 'r' in factorial of n
function power(n, r) {
       
    // Keep dividing n by powers of
    // 'r' and update count
    let count = 0;
    for (let i = r; (n / i) >= 1; i = i * r)
    count += n / i;
    return count;
}
 
// Driver code
 
    let n = 6, r = 3;
    document.write(power(n, r));
 
// This code is contributed by souravghosh0416.
</script>

Producción: 
 

2

Complejidad de Tiempo: O(log r) 
Espacio Auxiliar: O(1)

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.