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 the prime factorization of n!
Examples:
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
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 is added.
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) } |
Output:
3
Time Complexity: O(logpn)
Auxiliary Space: O(1)
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 the 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 then by till > 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 the implementation of the above steps.
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) } |
Output:
3
Time Complexity :O((n))
Auxiliary Space: O(1)
Contact Us