Problem 44749. Exponents in Factorials(hard)

This is problem is a harder version of "Problem 44747. Exponents in Factorials". https://ww2.mathworks.cn/matlabcentral/cody/problems/44747

It's time to get excited about numbers!!! Well, we're just dealing with factorials here, but it's still a good reason to get excited. You're given two numbers, n and k. Calculate the highest exponent of k that could appear in n!

For example, for n=5 and k=2, you're looking for the highest exponent of 2 that could appear in 5!, or 120. The highest power of 2 that evenly divides 120 is 3 (2^3 evenly divides 120, while 2^4 does not) so your output for maxexp(5,2)=3.

You can assume that both n and k are both integers greater than 1. 1<=n<=1e9, 2<=k<=100.