Tutorialspoint.dev

Largest power of k in n! (factorial) where k may not be prime

Given two numbers k and n, find the largest power of k that divides n!

Constraints:

 K > 1 

Examples:

Input : n = 7, k = 2
Output : 4
Explanation : 7! = 5040
The largest power of 2 that
divides 5040 is 24.

Input : n = 10, k = 9
Output :  2
The largest power of 9 that
divides 10! is 92.



We have discussed a solution in below post when k is always prime.

Legendre’s formula (Given p and n, find the largest x such that p^x divides n!)

Now to find the power of any non-prime number k in n!, we first find all the prime factors of the number k along with the count of number of their occurrences. Then for each prime factor, we count occurrences using Legendre’s formula which states that the largest possible power of a prime number p in n is ⌊n/p⌋ + ⌊n/(p2)⌋ + ⌊n/(p3)⌋ + ……

Over all the prime factors p of K, the one with the minimum value of findPowerOfK(n, p)/count will be our answer where count is number of occurrences of p in k.

// CPP program to find the largest power
// of k that divides n!
#include <bits/stdc++.h>
using namespace std;
  
// To find the power of a prime p in
// factorial N
int findPowerOfP(int n, int p)
{
    int count = 0;
    int r=p;
    while (r <= n) {
  
        // calculating floor(n/r)
        // and adding to the count
        count += (n / r);
  
        // increasing the power of p
        // from 1 to 2 to 3 and so on
        r = r * p;
    }
    return count;
}
  
// returns all the prime factors of k
vector<pair<int, int> > primeFactorsofK(int k)
{
    // vector to store all the prime factors
    // along with their number of occurrence
    // in factorization of k
    vector<pair<int, int> > ans;
  
    for (int i = 2; k != 1; i++) {
        if (k % i == 0) {
            int count = 0;
            while (k % i == 0) {
                k = k / i;
                count++;
            }
  
            ans.push_back(make_pair(i, count));
        }
    }
    return ans;
}
  
// Returns largest power of k that
// divides n!
int largestPowerOfK(int n, int k)
{
    vector<pair<int, int> > vec;
    vec = primeFactorsofK(k);
    int ans = INT_MAX;
    for (int i = 0; i < vec.size(); i++)
  
        // calculating minimum power of all
        // the prime factors of k
        ans = min(ans, findPowerOfP(n, 
              vec[i].first) / vec[i].second);
  
    return ans;
}
  
// Driver code
int main()
{
    cout << largestPowerOfK(7, 2) << endl;
    cout << largestPowerOfK(10, 9) << endl;
    return 0;
}

Output:

4
2

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

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter