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 $cn{t}_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 \cdots \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 +\cdots +\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})$