# calculates maximum p => factorial % divider^p == 0
def maxPowerOf(divider, factorial):
    sum = 0
    maxP = 0
    while(factorial/(divider**(maxP))>=1):
        maxP+=1
    curPow=divider;
    for i in range(1, maxP) :
        sum += int (factorial/curPow)
        curPow*=divider
    return sum

# number factorisation
def splitToDividers(num) :
   i = 2
   dividers = []
   while i* i <= num:
       while num % i == 0:
           dividers.append(i)
           num = num / i

       i = i + 1
   if num > 1:
       dividers.append(num)
   return dividers

# returns count of each divider, removes doubles from source
def processDividers(dividers) :
    countList = []
i = 0
    while i<len(dividers):
        j = i + 1
        countList.append(1)
        while j<len(dividers):
            if(dividers[i] == dividers[j]):
                del dividers[j]
                countList[i]+=1
                j -= 1
            j += 1
        i += 1
    return countList

inp = input().split()
number = int (inp[0])
base = int (inp[1])
 divs = splitToDividers(base)
counts = processDividers(divs)
minPower = maxPowerOf(divs[0], number)/counts[0]
for i in range(1, len(divs)) :
    curPower = maxPowerOf(divs[i], number)/counts[i]
    minPower = min(minPower, curPower)
print(int(minPower))