Tutorialspoint.dev

Finding power of prime number p in n!

Given a number ‘n’ and a prime number ‘p’. We need to find out the power of ‘p’ in prime factorization of n!

Examples:

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

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



Naive approach
The naive approach is to find the power of p in each number from 1 to n and add them.Because we know that during multiplication power are added.

C/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 n
        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 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

# Pyhton3 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) . " ";
   
// This code is contributed by 
// Akanksha Rai(Abby_akku)
?>


Output:

3

Efficient Approach
Before discussing efficient approach lets discuss a question given a two numbers n, m how many numbers are there from 1 to n that are divisible by m the answer is floor(n/m).
Now coming back to our original question to find power of p in n! what we do is count the number of numbers from 1 to n that are divisible by p then by p^2 then by p^3 till p^k > n and add them . This will be our required answer.

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

Below is implementation of above steps.

C/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 n
        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 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) . " ";
  
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>


Output:

3

Time Complexity :O(log_p(n))

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter