A factorial (of a large number) will usually contain some trailing zeros.
Your job is to make a function that calculates the number of trailing zeros, in any given base.

Factorial is defined like this:
```n! = 1 * 2 * 3 * 4 * ... * n-2 * n-1 * n```

Here's two examples to get you started:

```python
trailing_zeros(15, 10) == 3
#15! = 1307674368000, which has 3 zeros at the end

trailing_zeros(7, 2) == 4
#7! = 5030 = 0b1001110110000, which has 4 zeros at the end
```

Your code should be able to handle some very large numbers, so write some smart code.

Note: ```num``` will be a non-negative integer, ```base``` will be an integer larger or equal to two.

HINT: Should you not make any headway after trying a long time, you should try [this kata](https://www.codewars.com/kata/number-of-trailing-zeros-of-n) first.

Difficulty: interview

Starter code:

def trailing_zeros(num, base):
	

Solutions:
def isqrt(num):
    '''Compute int(sqrt(n)) for n integer > 0
    O(log4(n)) and no floating point operation, no division'''
    res, bit = 0, 1
    while bit <= num:
        bit <<= 2
    bit >>= 2

    while bit:
        if num >= res + bit:
            num -= res + bit
            res += bit << 1
        res >>= 1
        bit >>= 2
    return res

def factorize(n):
    for q in 2, 3:
        m = 0
        while not n % q:
            m += 1
            n //= q
        if m: yield q, m
    
    m, d, q, maxq = 0, 4, 1, isqrt(n)
    while q <= maxq:
        q, d = q + d, 6 - d
        while not n % q:
            m += 1
            n //= q
        if m:
            yield q, m
            m, d, q, maxq = 0, 4, 1, isqrt(n)
    if n > 1: yield n, 1

def count_factor(n, f):
    s = 0
    while n >= f:
        n //= f
        s += n
    return s

trailing_zeros = lambda n, b: min(count_factor(n, f)//m for f, m in factorize(b))

from collections import defaultdict

def pf(n):
    primes = defaultdict(lambda: 0); i=2
    while n>1 and i*i<=n:
        if n%i==0:
            while n%i==0: primes[i] = primes[i]+1; n/=i;
        i+=1
    if n>1: primes[n]=primes[n]+1
    return primes

reduce = lambda n,p: 0 if n<p else n//p + reduce(n//p,p)

def trailing_zeros(num, base):
    mx = float('inf'); primes = pf(base)
    for p in primes: mx = min(mx,reduce(num,p)//primes[p])
    return mx

def get_factors(n):
    r = []
    k = 2
    while k*k <= n:
        if n % k == 0:
            cnt = 0
            while n % k == 0:
                n /= k
                cnt += 1
            r.append((k, cnt))
        k += 1
    if n > 1:
        r.append((n, 1))
    return r

def trailing_zeros(num, base):
    factors = get_factors(base)
    zeros = 1<<10000 # infinity
    for f, p in factors:
        cnt = 0
        k = f
        while k <= num:
            cnt += num // k
            k *= f
        zeros = min(zeros, cnt // p)
    return zeros

def trailing_zeros(number, base):
    smallest_prime_by_pow = {}
    p = 2
    b = base
    while b > 1 and p * p <= base:
        count_p_pow = 0
        while b % p == 0:
            count_p_pow += 1
            b //= p

        if count_p_pow:
            smallest_prime_by_pow[count_p_pow] = p

        p += 1 if p == 2 else 2

    if b > 1:
        smallest_prime_by_pow[1] = b

    # print(smallest_prime_by_pow)
    res = number
    
    for count_p_pow, p in list(smallest_prime_by_pow.items()):
        count_p_in_fact = 0
        f = p
        while f <= number:
            # print(f, number // f)
            count_p_in_fact += number // f
            f *= p
        
        res = min(res, count_p_in_fact // count_p_pow)
        # print(count_p_in_fact)

    return res


f = lambda n, p: 0 if n < p else n//p + f(n//p, p)


def factors(n):
    p = 2
    while p*p <= n:
        cnt = 0
        while n % p == 0:
            cnt += 1
            n //= p
        yield p, cnt
        p += 1
    if n != 1:
        yield n, 1

def trailing_zeros(number, base):
    return min(f(number, num) // cnt for num, cnt in factors(base) if cnt != 0)

def factors(number):
    div = 2
    while div*div <= number:
        cnt = 0
        while number % div == 0:
            cnt += 1
            number //= div
        if cnt:
            yield div, cnt
        div += 1
    if number != 1:
        yield number, 1


def get_prime_power(n, p):
    res = 0
    div = p
    while div <= n:
        res += n // div
        div *= p
    return res
    
def trailing_zeros(number, base):
    return min(get_prime_power(number, num) // cnt for num, cnt in factors(base))

from itertools import cycle, groupby

def trailing_zeros(num, base):
    return min((exponent(num, p) // len(list(g)) for (p, g) in groupby(factor(base))))

def exponent(n, p):
    e = 0
    while n > 0:
        n //= p
        e += n
    return e

def factor(n):
    if n < 1: raise ValueError('factor: n must be > 0')
    for d in [2, 3, 5]:
        while n % d == 0:
            yield d
            n = n // d
    d = 7
    wheel = cycle([4, 2, 4, 2, 4, 6, 2, 6])
    while n > 1 and d * d <= n:
        if n % d == 0:
            yield d
            n = n // d
        else:
            d += next(wheel)
    if n > 1:
        yield n


def trailing_zeros(num, base):
    primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    plist = []
    pow = []
    b = base
    for p in primes:
        if b % p == 0:
            plist.append(p)
            ctr = 0
            while b % p == 0:
                b //= p
                ctr += 1
            pow.append(ctr)
    i = 101
    iinc = 2
    while  b > 1:
        if b % i == 0:
            if isprime(i):
                plist.append(i)
                ctr = 0
                while b % i == 0:
                    b = b // i
                    ctr += 1
                pow.append(ctr)
        i+=iinc
        iinc = 6 - iinc
        if i*i > b: i = b
    if len(plist) == 0: return 0
    plist.sort()
    accmax = 1e1000
    while len(plist)>0 :
        acc = 0
        a = plist[-1]    # biggest prime factor of base
        aa = pow[-1]
        n = num
        while n!=0:
            n = n // a
            acc += n
        acc = acc // aa
        plist.pop()
        pow.pop()
        if acc < accmax: accmax=acc
    return accmax

def isprime(n):
    if n<=1 : return False
    if n==2 or n==3: return True
    if n % 2 == 0: return False
    if n % 3 == 0: return False
    a=5
    ainc=2
    while a*a<=n:
        if n % a == 0: return False
        a += ainc
        ainc = 6-ainc
    return True



from gmpy2 import is_prime,next_prime
def trailing_zeros(n,b):
    F,p=[],1
    while 1<b:
        p,c=next_prime(p),0
        while b%p==0:b,c=b//p,c+1
        F+=[(p,c)]*(0<c)
        if is_prime(b):F,b=F+[(b,1)],1
    Z=[]
    for e,c in F:
        m,t=n,0
        while 1<m:m,t=m//e,t+m//e
        Z+=[t//c]
    return min(Z)

from gmpy2 import is_prime,next_prime
def trailing_zeros(n,b):
    F,p=[],1
    while 1<b:
        p,c=next_prime(p),0
        while b%p==0:b,c=b//p,c+1
        F+=[(p,c)]*(0<c)
        if is_prime(b):F,b=F+[(b,1)],1
    Z=[]
    for e,c in F:
        m,t=n,0
        while 1<m:
            m,_=divmod(m,e)
            t+=m
        Z+=[t//c]
    return min(Z)