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.
C++
Java
Python3
C#
Javascript
4 2
Time Complexity: O(k*log(n))
Auxiliary Space: O(k)
Approach 2: –Another approach to find the largest power of a non-prime number k in n! is by using the concept of the number of times a factor appears in a number’s prime factorization. The number of times a factor p appears in n! is given by the sum of the quotients n/p, n/p^2, n/p^3, and so on until the quotient becomes 0.
We can extend this concept to find the largest power of k in n! by considering the prime factorization of k. If k can be written as a product of primes, say k = p1^a1 * p2^a2 * … * pk^ak, then the largest power of k in n! is given by the minimum of the largest powers of each prime pi in k.
C++
Java
Python3
C#
Javascript
4 2
Time complexity:- O(sqrt(k) + log n).
Auxiliary Space: O(logN)
Contact Us