#!/usr/bin/env python3

# najdi prvočíselný rozklad čísla k
# vrať jej jako pole dvojic (prvočíslo, mocnina)
def factorize(k):
    p = 2
    factorization = []
    while p * p <= k: # stačí projít hodnoty do sqrt(k)
        # počet úspešných vydělení je mocnina u p v rozkladu
        exponent = 0
        while k % p == 0:
            k //= p
            exponent += 1
        # do výstupu přidej jen ta prvočísla, která v rozkladu figurují
        if exponent > 0:
            factorization.append( (p, exponent) )
        p += 1

    # zbytek může také ještě být prvočíslo
    if k > 1:
        factorization.append( (k, 1) )
    return factorization

# spočítej, kolikrát lze n! vydělit číslem p
# (jinými slovy, jaká je mocnina u p v rozkladu n!)
def calculate_prime_exponent_in_factorial(n, p):
    result = 0
    prime_power = p
    while prime_power <= n:
        result += n // prime_power # každý p-tý činitel je dělitelný p
        prime_power *= p # každý p-tý z nich je dělitelný znovu
    return result


N, K = map(int, input().split())
# rozhodující pro počet nul je nejméně zastoupený dělitel
zeros = min([calculate_prime_exponent_in_factorial(N, p) // e
             for p, e in factorize(K)])
print(zeros)