# 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.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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 > primeFactorsofK(``int` `k) ` `{ ` `    ``// vector to store all the prime factors ` `    ``// along with their number of occurrence ` `    ``// in factorization of k ` `    ``vector > 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 > 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
```