Given an integer n, find the power of a given prime number(r) in n!
Examples :
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
A simple method is to first calculate factorial of n, then factorize it to find the power of a prime number.
The above method can cause overflow for a slightly bigger numbers as factorial of a number is a big number. The idea is to consider prime factors of a factorial n.
Legendre Factorization of n!
For any prime number p and any integer n, let Vp(n) be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n). Then
Vp(n) = summation of floor(n / p^i) and i goes from 1 to infinity
While the formula on the right side is an infinite sum, for any particular values of n and p it has only finitely many nonzero terms: for every i large enough that p^i > n, one has floor(n/p^i) = 0 . since, the sum is convergent.
Power of ‘r’ in n! = floor(n/r) + floor(n/r^2) + floor(n/r^3) + ....
Program to count power of a no. r in n! based on above formula.
C++
// 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 nint 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 functionint main() { int n = 6, r = 3; printf(" %d ", power(n, r)); return 0;} |
Java
// 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 nstatic 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 codepublic static void main(String[] args) { int n = 6, r = 3; System.out.print(power(n, r));}}// This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find power # of a prime number ‘r’ in n!# Function to return power of a # no. 'r' in factorial of ndef 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 Coden = 6; r = 3print(power(n, r)) # This code is contributed by Smitha Dinesh Semwal. |
C#
// 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 nstatic 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 codepublic static void Main() { int n = 6, r = 3; Console.WriteLine(power(n, r));}}// This code is contributed by vt_m. |
PHP
<?php//PHP program to find power of // a prime number ‘r’ in n!// Function to return power of a // no. 'r' in factorial of nfunction 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?> |
Javascript
<script>// JavaScript program to find power of// a prime number 'r' in n!// Function to return power of a// no. 'r' in factorial of nfunction 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> |
Output:
2
Time Complexity: O(log r)
Auxiliary Space: O(1)
Please suggest if someone has a better solution which is more efficient in terms of space and time.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
