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 2^{4}. Input : n = 10, k = 9 Output : 2 The largest power of 9 that divides 10! is 9^{2}.

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/(p^{2})⌋ + ⌊n/(p^{3})⌋ + ……

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.

## leave a comment

## 0 Comments