¡Encontrar la potencia del número primo p en n!

Posted on by Rudeus Greyrat

Dado un número ‘n’ y un número primo ‘p’. ¡Necesitamos encontrar la potencia de ‘p’ en la descomposición en factores primos de n!
Ejemplos: 
 

Input  : n = 4, p = 2
Output : 3
         Power of 2 in the prime factorization
         of 2 in 4! = 24 is 3

Input  : n = 24, p = 2
Output : 22

Enfoque ingenuo 
El enfoque ingenuo consiste en encontrar la potencia de p en cada número del 1 an y sumarlos. Porque sabemos que durante la multiplicación se suma potencia.
 

C++

// C++ implementation of finding
// power of p in n!
#include <bits/stdc++.h>
 
using namespace std;
 
// Returns power of p in n!
int PowerOFPINnfactorial(int n, int p)
{
    // initializing answer
    int ans = 0;
 
    // initializing
    int temp = p;
 
    // loop until temp<=n
    while (temp <= n) {
 
        // add number of numbers divisible by temp
        ans += n / temp;
 
        // each time multiply temp by p
        temp = temp * p;
    }
    return ans;
}
 
// Driver function
int main()
{
    cout << PowerOFPINnfactorial(4, 2) << endl;
    return 0;
}

Java

// Java implementation of naive approach
 
public class GFG
{
    // Method to calculate the power of prime number p in n!
    static int PowerOFPINnfactorial(int n, int p)
    {
        // initializing answer
        int ans = 0;
      
        // finding power of p from 1 to n
        for (int i = 1; i <= n; i++) {
      
            // variable to note the power of p in i
            int count = 0, temp = i;
      
            // loop until temp is equal to i
            while (temp % p == 0) {
                count++;
                temp = temp / p;
            }
      
            // adding count to i
            ans += count;
        }
        return ans;
    }
     
    // Driver Method
    public static void main(String[] args)
    {
        System.out.println(PowerOFPINnfactorial(4, 2));
    }
}

Python3

# Python3 implementation of
# finding power of p in n!
 
# Returns power of p in n!
def PowerOFPINnfactorial(n, p):
 
    # initializing answer
    ans = 0;
 
    # initializing
    temp = p;
 
    # loop until temp<=n
    while (temp <= n):
 
        # add number of numbers
        # divisible by n
        ans += n / temp;
 
        # each time multiply
        # temp by p
        temp = temp * p;
         
    return ans;
 
# Driver Code
print(PowerOFPINnfactorial(4, 2));
 
# This code is contributed by
# mits

C#

// C# implementation of naive approach
using System;
 
public class GFG
{
    // Method to calculate power
    // of prime number p in n!
    static int PowerOFPINnfactorial(int n, int p)
    {
        // initializing answer
        int ans = 0;
     
        // finding power of p from 1 to n
        for (int i = 1; i <= n; i++) {
     
            // variable to note the power of p in i
            int count = 0, temp = i;
     
            // loop until temp is equal to i
            while (temp % p == 0) {
                count++;
                temp = temp / p;
            }
     
            // adding count to i
            ans += count;
        }
        return ans;
    }
     
    // Driver Code
    public static void Main(String []args)
    {
        Console.WriteLine(PowerOFPINnfactorial(4, 2));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP implementation of
// finding power of p in n!
  
// Returns power of p in n!
function PowerOFPINnfactorial($n, $p)
{
    // initializing answer
    $ans = 0;
  
    // initializing
    $temp = $p;
  
    // loop until temp<=n
    while ($temp <= $n)
    {
  
        // add number of numbers
        // divisible by n
        $ans += $n / $temp;
  
        // each time multiply
        // temp by p
        $temp = $temp * $p;
    }
    return $ans;
}
  
// Driver Code
echo PowerOFPINnfactorial(4, 2) . "\n";
  
// This code is contributed by
// Akanksha Rai(Abby_akku)
?>

Javascript

<script>
 
// Javascript implementation of
// finding power of p in n!
  
// Returns power of p in n!
function PowerOFPINnfactorial(n, p)
{
    // initializing answer
    let ans = 0;
  
    // initializing
    let temp = p;
  
    // loop until temp<=n
    while (temp <= n)
    {
  
        // add number of numbers
        // divisible by n
        ans += n / temp;
  
        // each time multiply
        // temp by p
        temp = temp * p;
    }
    return ans;
}
  
// Driver Code
document.write(PowerOFPINnfactorial(4, 2));
  
// This code is contributed by _saurabh_jaiswal
 
</script>

Kotlin

//function to find the power of p in n! in Kotlin
fun PowerOFPINnfactorial(n: Int, p: Int)
{
    // initializing answer
    var ans = 0;
 
    // initializing
    var temp = p;
 
    // loop until temp<=n
    while(temp<=n)
    {
        // add number of numbers divisible by temp
        ans+=n/temp;
         
        // each time multiply temp by p
        temp*=p;
    }
 
    println(ans)
}
 
//Driver Code
fun main(args: Array<String>)
{
    val n = 4
    val p = 2
    PowerOFPINnfactorial(n,p)
}

Producción: 

3

Complejidad temporal: O(log p n) 
Espacio auxiliar: O(1)

Enfoque eficiente 
Antes de discutir el enfoque eficiente, hablemos de una pregunta dados dos números n, m, ¿cuántos números hay del 1 al n que son divisibles por m? La respuesta es piso (n/m). 
¡Ahora volviendo a nuestra pregunta original para encontrar la potencia de p en n! lo que hacemos es contar el número de números del 1 al n que son divisibles por p y luego por  p^2 hasta  p^3 >  p^k n y sumarlos. Esta será nuestra respuesta requerida. 

   Powerofp(n!) = floor(n/p) + floor(n/p^2) + floor(n/p^3)........

A continuación se muestra la implementación de los pasos anteriores.
 

C++

// C++ implementation of finding power of p in n!
#include <bits/stdc++.h>
 
using namespace std;
 
// Returns power of p in n!
int PowerOFPINnfactorial(int n, int p)
{
    // initializing answer
    int ans = 0;
 
    // initializing
    int temp = p;
 
    // loop until temp<=n
    while (temp <= n) {
 
        // add number of numbers divisible by temp
        ans += n / temp;
 
        // each time multiply temp by p
        temp = temp * p;
    }
    return ans;
}
 
// Driver function
int main()
{
    cout << PowerOFPINnfactorial(4, 2) << endl;
    return 0;
}

Java

// Java implementation of finding power of p in n!
 
public class GFG
{
    // Method to calculate the power of prime number p in n!
    static int PowerOFPINnfactorial(int n, int p)
    {
        // initializing answer
        int ans = 0;
      
        // initializing
        int temp = p;
      
        // loop until temp<=n
        while (temp <= n) {
      
            // add number of numbers divisible by n
            ans += n / temp;
      
            // each time multiply temp by p
            temp = temp * p;
        }
        return ans;
    }
     
    // Driver Method
    public static void main(String[] args)
    {
        System.out.println(PowerOFPINnfactorial(4, 2));
    }
}

Python3

# Python3 implementation of
# finding power of p in n!
 
# Returns power of p in n!
def PowerOFPINnfactorial(n, p):
 
    # initializing answer
    ans = 0
 
    # initializing
    temp = p
 
    # loop until temp<=n
    while (temp <= n) :
 
        # add number of numbers
        # divisible by n
        ans += n / temp
 
        # each time multiply
        # temp by p
        temp = temp * p
     
    return int(ans)
 
# Driver Code
print(PowerOFPINnfactorial(4, 2))
 
# This code is contributed
# by Smitha

C#

// C# implementation of finding
// power of p in n!
using System;
 
public class GFG
{
 
    // Method to calculate power
    // of prime number p in n!
    static int PowerOFPINnfactorial(int n, int p)
    {
        // initializing answer
        int ans = 0;
     
        // initializing
        int temp = p;
     
        // loop until temp <= n
        while (temp <= n) {
     
            // add number of numbers divisible by n
            ans += n / temp;
     
            // each time multiply temp by p
            temp = temp * p;
        }
        return ans;
    }
     
    // Driver Code
    public static void Main(String []args)
    {
        Console.WriteLine(PowerOFPINnfactorial(4, 2));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP implementation of
// finding power of p in n!
 
// Returns power of p in n!
function PowerOFPINnfactorial($n, $p)
{
    // initializing answer
    $ans = 0;
 
    // initializing
    $temp = $p;
 
    // loop until temp<=n
    while ($temp <= $n)
    {
 
        // add number of numbers divisible by n
        $ans += $n / $temp;
 
        // each time multiply temp by p
        $temp = $temp * $p;
    }
    return $ans;
}
 
// Driver function
echo PowerOFPINnfactorial(4, 2) . "\n";
 
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>

Javascript

<script>
 
// Javascript implementation of
// finding power of p in n!
 
// Returns power of p in n!
function PowerOFPINnfactorial(n, p)
{
    // initializing answer
    let ans = 0;
 
    // initializing
    let temp = p;
 
    // loop until temp<=n
    while (temp <= n)
    {
 
        // add number of numbers divisible by n
        ans += n / temp;
 
        // each time multiply temp by p
        temp = temp * p;
    }
    return ans;
}
 
// Driver function
document.write(PowerOFPINnfactorial(4, 2));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Kotlin

//function to find the power of p in n! in Kotlin
fun PowerOFPINnfactorial(n: Int, p: Int)
{
    // initializing answer
    var ans = 0;
 
    // initializing
    var temp = p;
 
    // loop until temp<=n
    while(temp<=n)
    {
        // add number of numbers divisible by temp
        ans+=n/temp;
         
        // each time multiply temp by p
        temp*=p;
    }
 
    println(ans)
}
 
//Driver Code
fun main(args: Array<String>)
{
    val n = 4
    val p = 2
    PowerOFPINnfactorial(n,p)
}

Producción: 

3

Complejidad del tiempo : O ( log_p (n))
Espacio auxiliar: O (1)
Este artículo es una contribución de Aarti_Rathi y Ayush Jha . 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *