Let ~A~ and ~cnt~ be the list of prime factors and the list of their respective frequencies in the prime factorization of ~a~. The elements of ~A~ can be obtained through prime factorizing ~a~. Now, for each ~A_i~ in ~A~, we find ~n_i~: the greatest integer value that ~cnt_i~ can be multiplied by, and remain not greater than the number of times ~A_i~ appears in the prime factorization of ~b!~. The answer is the minimum over all ~n_i~.

For example, consider Sample Input 1, with ~a = 8~, ~b = 849~. After prime factorizing, ~A = [2]~ and ~cnt = [3]~. Now consider how many times ~2~ occurs in the expansion of ~849! = 1 \times 2 \times \dots \times 849~. Every two numbers in the expansion of ~849! = 1 \times 2 \times \dots~ have ~2~ as a factor, and there are ~\lfloor\frac{849}{2}\rfloor = 424~ such numbers. However, for elements which are divisible by ~2^2 = 4~ in the expansion, there is still one ~2~ which we have not yet considered. Similarly, there are ~\lfloor\frac{849}{4}\rfloor = 212~ such elements. For elements which are divisible by ~2^3 = 8~, there is yet one more ~2~ which we have not considered, and the pattern continues. We will find that in total, there are ~\lfloor\frac{849}{2}\rfloor+\lfloor\frac{849}{4}\rfloor+\lfloor\frac{849}{8}\rfloor+\lfloor\frac{849}{16}\rfloor+\dots+\lfloor\frac{849}{512}\rfloor = 424+212+106+53+26+13+6+3+1 = 844~ occurrences of ~2~ in the prime factorization of ~849!~. Now, we find ~n_i~, which is ~\lfloor\frac{844}{3}\rfloor = 241~. Since there is only one such ~n_i~, this is our answer.

Note: ~\lfloor x \rfloor~ means ~x~, rounded down to the nearest integer.

Pseudocode:

read a, b

(prime factorize a)

for i in [2, sqrt(a)]
    if a is divisible by i
        append i to A
    while a is divisible by i
        a /= i
        cnt[i]++

if a != 1
    insert a into A
    cnt[a]++

(find all n_i)

n = MAXIMUM_VALUE
for A_i in A
    occurrences = 0
    looking_for = A_i
    while b / looking_for != 0
        occurrences += b / looking_for
        looking_for *= A_i
    n_i = occurrences / cnt[A_i]
    n = min(n, n_i)

print n

Time complexity: ~\mathcal O(\sqrt{n}+\frac{\log^2 n}{\log \log n})~