How to optimize Python code as much as possible?

Question

Python

from math import factorial
N, base = map(int,input().split())

NN = factorial(N)
def d(n, b):
    d.t = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    r=''
    while n:
        n, y = divmod(n, b)
        r=d.t[y]+r
    return r

f = str(d(NN, base)[::-1])
a = len(f)
p = 0
for i in f:
    if i == '0':
        p += 1
    else:
        break
print(p)

code does not pass tests on time, help optimize)

Answer 1

The problem is not in the code, but in the algorithm. It takes a long time to build the entire string and count zeros in it.
There is such a formula . For every prime number, you can determine the power simply by dividing n (not a factorial!) by that prime number integer until you get 0 and sum up all the results.
But this only works for prime numbers. Those. to find out to what extent the number 10 is included in N! (or how many zeros at the end in decimal notation) you need to find out how many times 2 and 5 are included in N! and take the minimum.
Those. it is necessary to decompose k into prime factors, for each prime factor count how many times it is included in n! according to the formula above. Then divide this by the power of a prime number in k, and take the minimum over all divisors of k.