The number "zero" is called "love" (or "l'oeuf" to be precise, literally means "egg" in French), for example when denoting the zero score in a game of tennis. 

Aki is fond of numbers, especially those with trailing zeros. For example, the number $9200$ has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is.

However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers.

Given two integers $n$ and $b$ (in decimal notation), your task is to calculate the number of trailing zero digits in the $b$-ary (in the base/radix of $b$) representation of $n\,!$ (factorial of $n$). 


-----Input-----

The only line of the input contains two integers $n$ and $b$ ($1 \le n \le 10^{18}$, $2 \le b \le 10^{12}$).


-----Output-----

Print an only integer — the number of trailing zero digits in the $b$-ary representation of $n!$


-----Examples-----
Input
6 9

Output
1

Input
38 11

Output
3

Input
5 2

Output
3

Input
5 10

Output
1



-----Note-----

In the first example, $6!_{(10)} = 720_{(10)} = 880_{(9)}$.

In the third and fourth example, $5!_{(10)} = 120_{(10)} = 1111000_{(2)}$.

The representation of the number $x$ in the $b$-ary base is $d_1, d_2, \ldots, d_k$ if $x = d_1 b^{k - 1} + d_2 b^{k - 2} + \ldots + d_k b^0$, where $d_i$ are integers and $0 \le d_i \le b - 1$. For example, the number $720$ from the first example is represented as $880_{(9)}$ since $720 = 8 \cdot 9^2 + 8 \cdot 9 + 0 \cdot 1$.

You can read more about bases here.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Number theory

Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
def Getprime(goal):
	ans = []
	if goal % 2 == 0:
		cnt = 0
		while goal % 2 == 0:
			goal //= 2
			cnt += 1
		ans.append([2, cnt])
	i = 3
	while i * i <= goal:
		if goal % i == 0:
			cnt = 0
			while goal % i == 0:
				goal //= i
				cnt += 1
				ans.append([i, cnt])
		i += 2
	if goal != 1:
		ans.append([goal, 1])
	return ans

def find(g, p):
	ans = 0
	t = p
	while t <= g:
		ans += g // t
		t *= p
	return ans
ans = input().split()
n = int(ans[0])
b = int(ans[1])
temp = Getprime(b)
sz = len(temp)
ans = find(n, temp[0][0]) // temp[0][1]
i = 1
while i < sz:
	now = find(n, temp[i][0]) // temp[i][1]
	if now < ans:
		ans = now
	i += 1
print(ans)


def factorize(x):
	(dictionary, i) = ({}, 2)
	while i * i <= x:
		exp = 0
		while x % i == 0:
			(exp, x) = (exp + 1, x // i)
		if exp > 0:
			dictionary[i] = exp
		i = i + 1
	if x > 1:
		dictionary[x] = 1
	return dictionary

def get_exponential_from_factorial(n, prime):
	ans = 0
	while n > 0:
		ans += n // prime
		n //= prime
	return ans
(n, b) = map(int, input().split())
b_prime_factors = factorize(b)
trailing = float('inf')
for prime in b_prime_factors:
	trailing = min(trailing, get_exponential_from_factorial(n, prime) // b_prime_factors[prime])
print(trailing)


(n, k) = list(map(int, input().split()))
primes = []
N = n
K = k
from collections import defaultdict
d = defaultdict(lambda : 0)
while k % 2 == 0:
	d[2] += 1
	k //= 2
for i in range(2, k + 1):
	if i * i > k:
		break
	while k % i == 0:
		d[i] += 1
		k //= i
if k > 2:
	d[k] = 1
k = K
temp = list(d.keys())
temp.sort()
ans = 1000000000000000000
for i in temp:
	mv = i
	mi = d[i]
	c = 0
	factor = mv
	n = N
	while n // factor != 0:
		c += n // factor
		factor *= mv
	ans = min(ans, c // mi)
print(ans)


(n, b) = map(int, input().split())
temp = b
pf = []
from math import sqrt as S
for i in range(2, int(S(b)) + 1):
	if b % i == 0:
		c = 0
		while b % i == 0:
			c += 1
			b = b // i
		pf.append([c, i])
if b > 1:
	pf.append([1, b])
plen = len(pf)

def chk(z, p):
	ct = 0
	k = p
	while z // k > 0:
		ct += z // k
		k = k * p
	return ct
mini = 10 ** 50
for i in range(plen):
	currp = pf[i][1]
	cnt = pf[i][0]
	cur = chk(n, currp)
	mini = min(mini, cur // cnt)
print(mini)


(n, b) = list(map(int, input().split()))
primes = []

def seive():
	nn = 1000100
	vis = [False] * nn
	for i in range(4, nn, 2):
		vis[i] = True
	i = 3
	(vis[0], vis[1]) = (True, True)
	while i * i < nn:
		if not vis[i]:
			j = i * i
			while j < nn:
				vis[j] = True
				j += 2 * i
		i += 2
	for i in range(nn):
		if not vis[i]:
			primes.append(i)
seive()

def find_factors(nn):
	ans = []
	for i in primes:
		if nn % i == 0:
			count = 0
			while nn % i == 0:
				count += 1
				nn /= i
			ans.append((i, count))
	if nn > 1:
		ans.append((nn, 1))
	return ans
f = find_factors(b)

def find_ans(t):
	(ff, no) = t
	ans = 0
	temp = ff
	while n // ff:
		ans += n // ff
		ff *= temp
	return ans // no
final_ans = find_ans(f[0])
for i in range(1, len(f)):
	final_ans = min(final_ans, find_ans(f[i]))
print(int(final_ans))


import math
(n, b) = map(int, input().split())
t = b
dic = {}
while True:
	if t % 2 == 0:
		dic[2] = 0
		while t % 2 == 0:
			t = t // 2
			dic[2] += 1
	for i in range(3, int(math.sqrt(b)) + 1, 2):
		if t % i == 0:
			dic[i] = 0
			while t % i == 0:
				dic[i] += 1
				t = t // i
	if t != 1:
		dic[t] = 1
	break
dic2 = {i: 0 for i in dic.keys()}
m = float('inf')
for i in dic.keys():
	c = 1
	while n // pow(i, c) > 0:
		dic2[i] += n // pow(i, c)
		c += 1
	m = min(m, dic2[i] // dic[i])
print(m)


from math import gcd, sqrt
(n, b) = map(int, input().split())
delit = list()
i = 2
while i <= sqrt(b) + 1:
	if b % i == 0:
		delit.append(i)
		b //= i
	else:
		i += 1
if b != 1:
	delit.append(b)
need_delit = dict()
top_delit = set(delit)
for i in top_delit:
	need_delit[i] = 0
for i in delit:
	need_delit[i] += 1
num_delit = dict()
for i in top_delit:
	num_delit[i] = 0
	j = i
	while j <= n:
		num_delit[i] += n // j
		j *= i
ans = n * n * n
for i in num_delit:
	ans = min(ans, num_delit[i] // need_delit[i])
print(ans)


import math
(n, b) = map(int, input().split())
ans = int(-1)

def get(x):
	pw = x
	cnt = 0
	while pw <= n:
		cnt += n // pw
		pw *= x
	return cnt
for i in range(2, int(math.sqrt(b)) + 1):
	if b % i != 0:
		continue
	cnt = 0
	while b % i == 0:
		cnt += 1
		b //= i
	if ans == -1:
		ans = get(i) // cnt
	else:
		ans = min(ans, get(i) // cnt)
if b != 1:
	if ans == -1:
		ans = get(b)
	else:
		ans = min(ans, get(b))
print(int(ans))


(n, b) = map(int, input().split())
d = 10 ** 25
i = 2
while b != 1:
	if i * i > b:
		i = b
	if b % i == 0:
		cntb = 0
		cntn = 0
		nn = n
		while b % i == 0:
			b //= i
			cntb += 1
		while nn >= i:
			nn //= i
			cntn += nn
		d = min(d, cntn // cntb)
	i += 1
print(d)


def f(p, q, n):
	w = p
	r = 0
	while w <= n:
		r += n // w
		w *= p
	return r // q
(n, k) = list(map(int, input().split()))
i = 2
s = -1
while i * i <= k:
	if k % i == 0:
		cnt = 0
		while k % i == 0:
			k //= i
			cnt += 1
		j = f(i, cnt, n)
		if s < 0 or s > j:
			s = j
	i += 1
if k > 1:
	j = f(k, 1, n)
	if s > j or s < 0:
		s = j
print(s)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import sqrt
(n, k) = list(map(int, input().split()))
mp = {}
kek = sqrt(k) + 1
for i in range(2, int(kek)):
	if k % i == 0:
		mp[i] = 0
	while k % i == 0:
		k //= i
		mp[i] += 1
if k != 1:
	mp[k] = 1
lel = pow(10, 100)
for x in mp:
	nn = n
	cnt = 0
	while nn >= x:
		cnt += nn // x
		nn //= x
	lel = min(lel, cnt // mp[x])
print(lel)


import math
s = input().split()
(n, b) = (int(s[0]), int(s[1]))
sqrtn = math.ceil(math.sqrt(b)) + 1
p = []
e = []
ntmp = b
for i in range(2, sqrtn + 1):
	if ntmp == 1:
		break
	if ntmp % i == 0:
		cnt = 0
		while ntmp % i == 0:
			cnt += 1
			ntmp //= i
		p.append(i)
		e.append(cnt)
if ntmp != 1:
	p.append(int(ntmp))
	e.append(1)
m = [0] * len(p)
for i in range(len(p)):
	ntmp = n
	while ntmp:
		ntmp //= p[i]
		m[i] += ntmp
u = min([m[i] // e[i] for i in range(len(p))])
print(u)


def start(x, cnt):
	global ans
	i = x
	res = 0
	while i <= n:
		res += n // i
		i *= x
	ans = min(ans, res // cnt)
(n, b) = map(int, input().split())
nb = b
ans = 1e+20
i = 2
while i * i <= b:
	if nb % i == 0:
		cnt = 0
		while nb % i == 0:
			cnt += 1
			nb //= i
		start(i, cnt)
	i += 1
if nb > 1:
	start(nb, 1)
print(ans)


import sys
from collections import Counter

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip('\n')
fac = []

def primefactor(n):
	while n % 2 == 0:
		n //= 2
		fac.append(2)
	for k in range(3, int(n ** 0.5) + 1, 2):
		while n % k == 0:
			n //= k
			fac.append(k)
	if n != 1:
		fac.append(n)
(n, b) = map(int, input().split())
primefactor(b)
d = Counter(fac)
ans = 30 ** 18
for i in sorted(d.keys()):
	j = i
	new = 0
	while n // j != 0:
		new += n // j
		j *= i
	ans = min(ans, new // d[i])
print(ans)


(n, b) = map(int, input().split(' '))

def factor(b):
	fac = {}
	for i in range(2, int(b ** 0.5) + 1):
		if b % i == 0:
			fac[i] = 0
		while b % i == 0:
			fac[i] += 1
			b = b // i
		if b == 1:
			break
	if b > 1:
		if b not in fac:
			fac[b] = 0
		fac[b] += 1
	return fac
m = factor(b)
ans = 111111111111111111111
for k in m.keys():
	denom = k
	exp = 0
	while n // denom > 0:
		exp += n // denom
		denom *= k
	ans = min(ans, exp // m[k])
print(ans)


(n, b) = map(int, input().split())
a = []
d = 2
while True:
	count = 0
	while b % d == 0:
		count += 1
		b //= d
	if count > 0:
		a.append([d, count])
	d += 1
	if d * d > b:
		break
if b > 1:
	a.append([b, 1])
cmin = -1
for i in a:
	dtek = i[0]
	ptek = 1
	ctek = 0
	d = dtek
	while d <= n:
		ctek += n // d
		d *= dtek
		ptek += 1
	c = ctek // i[1]
	if cmin == -1 or c < cmin:
		cmin = c
print(cmin)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	(n, b) = sep()
	pr = {}
	for i in range(2, floor(b ** 0.5) + 1):
		if b % i == 0:
			cnt = 0
			while b % i == 0:
				b //= i
				cnt += 1
			pr[i] = cnt
	if b != 1:
		pr[b] = 1
	cnt = {}
	for i in pr:
		curr = i
		x = 0
		while curr <= n:
			x += n // curr
			curr *= i
		cnt[i] = x
	mn = inf
	for i in cnt:
		mn = min(mn, cnt[i] // pr[i])
	print(mn)
testcase(1)


from collections import Counter
import math
(n, b) = map(int, input().split())

def primeFactors(n):
	while n % 2 == 0:
		p.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			p.append(i)
			n = n / i
	if n > 2:
		p.append(n)
p = []
primeFactors(b)
m = []
for i in p:
	v = i
	e = n
	s = 0
	while e:
		e = math.floor(e // v)
		s = s + e
	m.append(s)
l = Counter(p)
zp = zip(p, m)
b = []
for (i, j) in zp:
	b.append(j // l[i])
print(min(b))


from math import sqrt as s
(n, b) = map(int, input().split())

def FactErPechonerZero(n, p):
	b = 1
	a = 1
	c = 0
	while 1:
		a = a * p
		b = n // a
		if b > 0:
			c += b
		else:
			break
	return c
i = 2
temp = b
x = []
while i * i <= temp:
	count = 0
	while b % i == 0:
		b = b // i
		count += 1
	if count > 0:
		x.append((count, i))
	i += 1
if b > 1:
	x.append((1, b))
x.sort()
ans = pow(10, 18) + 5
for i in range(len(x)):
	z = FactErPechonerZero(n, x[i][1])
	ans = min(ans, z // x[i][0])
print(ans)


(n, b) = map(int, input().split())
f = []
p = []
i = 2
bb = b
while i * i <= bb:
	if b % i == 0:
		p.append(i)
		f.append(0)
		while b % i == 0:
			b = b // i
			f[-1] += 1
	i += 1
if b != 1:
	p.append(b)
	f.append(1)
ncopy = n
for i in range(len(p)):
	n = ncopy
	ai = 0
	x = p[i]
	while n // x > 0:
		ai += n // x
		x = x * p[i]
	p[i] = ai // f[i]
print(min(p))


(n, b) = map(int, input().split())
ans = 1000000000000000000
for i in range(2, b + 1):
	if 1 * i * i > b:
		i = b
	cnt = 0
	while b % i == 0:
		b //= i
		cnt += 1
	if cnt == 0:
		continue
	tmp = 0
	mul = 1
	while mul <= n // i:
		mul *= i
		tmp += n // mul
	ans = min(ans, tmp // cnt)
	if i > b:
		break
print(int(ans))


(n, b) = map(int, input().split())
(i, ans) = (2, 18446744073709551615)
while i <= b:
	if i * i > b:
		i = b
	cnt = 0
	while b % i == 0:
		(cnt, b) = (cnt + 1, b // i)
	if cnt != 0:
		(x, tmp) = (i, 0)
		while x <= n:
			(tmp, x) = (tmp + n // x, x * i)
		ans = min(ans, tmp // cnt)
	i += 1
print(ans)


import math, time
facts = []
fcounts = []

def primefactors(n):
	c = 0
	if n % 2 == 0:
		while n % 2 == 0:
			c += 1
			n = n // 2
		facts.append(2)
		fcounts.append(c)
	for i in range(3, int(math.sqrt(n) + 1), 2):
		c = 0
		if n % i == 0:
			while n % i == 0:
				c += 1
				n = n // i
			facts.append(i)
			fcounts.append(c)
	if n > 2:
		facts.append(n)
		fcounts.append(1)

def task(x, u):
	t = 0
	p = u
	while True:
		if x < p:
			return t
		else:
			t += x // p
		p *= u
(n, b) = map(int, input().split())
primefactors(b)
l = len(facts)
val = int(1e+18)
for i in range(l):
	x = facts[i]
	a = task(n, x)
	val = min(val, a // fcounts[i])
if val is int(1e+18):
	print('0')
else:
	print(int(val))


from math import sqrt
(n, b) = [int(i) for i in input().split()]

def geg(n, k, l):
	if k <= n:
		return n // k + geg(n, k * l, l)
	else:
		return 0

def fact(b, n):
	D = {}
	for i in range(2, round(sqrt(b)) + 1):
		if b % i == 0:
			s = 0
			while b % i == 0:
				b = b // i
				s += 1
			D[i] = s
	L = []
	for i in D.keys():
		L.append(geg(n, i, i) // D[i])
	if b != 1:
		L.append(geg(n, b, b))
	m = L[0]
	for i in L:
		if m > i:
			m = i
	return m
print(fact(b, n))


import math
r = [int(x) for x in input().split()]
n = r[0]
b = r[1]
temp = b
simple = {}
ov = {}
i = 2
while i * i <= b:
	while temp % i == 0:
		if simple.get(i) == None:
			simple[i] = 1
		else:
			simple[i] += 1
		temp //= i
	i += 1
if temp != 1:
	if simple.get(temp) == None:
		simple[temp] = 1
	else:
		simple[temp] += 1
for x in simple.keys():
	step = x
	otv = 0
	while step <= n:
		otv += n // step
		step *= x
	ov[x] = int(otv)
r = 10 ** 100
for x in ov.keys():
	r = min(r, ov[x] // simple[x])
print(r)


from copy import deepcopy
(n, b) = map(int, input().split())
i = 2
arr = []
c_n = n
while i * i <= b:
	t = 0
	while b % i == 0:
		t += 1
		b /= i
	if t:
		arr.append((i, t))
	i += 1
if b != 1:
	arr.append((int(b), 1))
mn = None
for (i, t) in arr:
	c_n = n
	k = 0
	while c_n >= i:
		k += c_n // i
		c_n //= i
	if mn is None:
		mn = k // t
	mn = min(mn, k // t)
print(int(mn))


import math

def isprime(x):
	for i in range(2, int(math.sqrt(x)) + 1):
		if x % i == 0:
			return False
	return True

def factor(w):
	fac = []
	i = 2
	while i <= math.sqrt(w):
		if w % i == 0:
			if w / i == i and isprime(i):
				fac.append(i)
			else:
				if isprime(i):
					fac.append(i)
				if isprime(w // i):
					fac.append(w // i)
		i += 1
	if isprime(w):
		fac.append(w)
	return fac

def ans(nu, n):
	c = 0
	val = n
	while val // nu > 0:
		c += val // nu
		val = val // nu
	return c

def get(nuu, bu):
	c = 0
	val = bu
	while val % nuu == 0:
		c += 1
		val = val // nuu
	return c
(n, b) = map(int, input().split())
need = factor(b)
mini = 9999999999999999999999
for i in range(len(need)):
	count = ans(need[i], n)
	count1 = get(need[i], b)
	if count // count1 < mini:
		mini = count // count1
print(mini)


(n, k) = map(int, input().split())
ans = 1e+18
d = 2
while k != 1:
	c = k
	cnt = 0
	if d * d > k:
		d = k
	while k % d == 0:
		cnt += 1
		k //= d
	if cnt == 0:
		d += 1
		continue
	res = 0
	i = d
	while i <= n:
		res += n // i
		i *= d
	ans = min(ans, res // cnt)
	d += 1
print(ans)


from math import sqrt

def fact(a):
	nonlocal g
	nonlocal h
	for i in range(2, int(sqrt(a)) + 1):
		k = 0
		if a % i == 0:
			g.append(i)
		while a % i == 0:
			a = a // i
			k += 1
		if k != 0:
			h.append(k)
	if a > 1:
		g.append(a)
		h.append(1)
(n, k) = list(map(int, input().split()))
g = []
h = []
f = fact(k)
mini = 100000000000000000000000000000000000000000000000000000000000
for i in range(len(g)):
	k1 = 0
	v = g[i]
	while n // g[i] > 0:
		k1 += n // g[i]
		g[i] *= v
	if k1 // h[i] < mini:
		mini = k1 // h[i]
print(mini)


from math import floor
arr = input().split()
a = int(arr[1])
f = int(arr[0])
bound = floor(a ** 0.5)
test = a
prime = []
count = []
for x in range(2, bound + 1):
	if test % x == 0:
		s_count = 1
		test //= x
		while test % x == 0:
			test //= x
			s_count += 1
		prime.append(x)
		count.append(s_count)
		bound = floor(test ** 0.5)
if test != 1:
	prime.append(test)
	count.append(1)
smallest = f
for x in range(len(prime)):
	rep = 0
	hold = f
	while hold != 0:
		hold //= prime[x]
		rep += hold
	smallest = min(smallest, rep // count[x])
print(smallest)


def main():
	(n, b) = map(int, input().split())
	(i, ans) = (2, 10 ** 19)
	while i <= b:
		if i * i > b:
			i = b
		(cnt, temp, x) = (0, 0, 1)
		while b % i == 0:
			b //= i
			cnt += 1
		if cnt == 0:
			i += 1
			continue
		while x <= n // i:
			x *= i
			temp += n // x
		ans = min(ans, temp // cnt)
		i += 1
	print(ans)
main()


def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
(n, b) = map(int, input().split())
prime = prime_factors(b)
minimum = 10 ** 18
for i in set(prime):
	total = 0
	num = prime.count(i)
	temp = n
	while temp != 0:
		temp //= i
		total += temp
	total //= num
	if total < minimum:
		minimum = total
print(minimum)


(b, a) = list(map(int, input().split()))
delit = []
st = []
i = 2
uk = -1
while i * i <= a:
	if a % i == 0:
		delit.append(i)
		uk += 1
		st.append(0)
		while a % i == 0:
			a //= i
			st[uk] += 1
	i += 1
if a > 1:
	delit.append(a)
	st.append(1)
coun = 0
colvo = [0] * len(st)
cop = b
for i in range(len(delit)):
	while cop >= delit[i]:
		colvo[i] += cop // delit[i]
		cop //= delit[i]
	cop = b
coun = colvo[i] // st[i]
for i in range(len(st)):
	if colvo[i] // st[i] < coun:
		coun = colvo[i] // st[i]
print(coun)


import math

def p(n):
	a = []
	while n % 2 == 0:
		a.append(int(2))
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			a.append(int(i))
			n = n / i
	if n > 2:
		a.append(int(n))
	return a

def solve(m, q, i):
	j = 2
	s = int(m // int(math.pow(i, 1)))
	r = int(m // int(math.pow(i, 1)))
	while r != 0:
		r = int(m // int(math.pow(i, j)))
		s += r
		j += 1
	l = int(s // q)
	return l
(n, m) = map(int, input().split())
c = dict()
d = p(m)
for j in range(len(d)):
	if d[j] in c.keys():
		c[d[j]] += 1
	else:
		c[d[j]] = 1
f = set(d)
m = 10000000000000000000000000000
for j in f:
	q = c[j]
	s = solve(n, q, j)
	if s < m:
		m = s
print(m)


(n, x) = map(int, input().split())
import math
L = int(math.sqrt(x))
FACT = dict()
for i in range(2, L + 2):
	while x % i == 0:
		FACT[i] = FACT.get(i, 0) + 1
		x = x // i
if x != 1:
	FACT[x] = FACT.get(x, 0) + 1
ANS = float('inf')
for f in FACT:
	ANS_f = 0
	x = f
	while x <= n:
		ANS_f += n // x
		x *= f
	ANS = min(ANS, ANS_f // FACT[f])
print(ANS)


import decimal
input_ = input().split()
n = int(input_[0])
b = int(input_[1])

def find_simple(b):
	i = 2
	primfac = {}
	while i * i <= b:
		primfac.update({i: 0})
		while b % i == 0:
			primfac.update({i: primfac[i] + 1})
			b /= i
		if primfac.get(i) == 0:
			primfac.pop(i)
		i += 1
	if b > 1:
		primfac.update({b: 1})
	return primfac

def find_need(n, dict_):
	need_fact = {}
	for key in dict_.keys():
		need_fact.update({key: decimal.Decimal(0)})
		key_ = key
		while key_ <= n:
			need_fact.update({key: need_fact[key] + decimal.Decimal(n // key_)})
			key_ *= key
	return need_fact

def find_count(dict_prim, dict_fact):
	counts = []
	for key in dict_prim.keys():
		counts.append(dict_fact[key] // dict_prim[key])
	return counts
if n == 1:
	print('0')
	exit()
if n == 2:
	if b == 2:
		print('1')
	else:
		print('0')
	exit()
simple = find_simple(b)
print(int(min(find_count(simple, find_need(n, simple)))))


def to_prime(k):
	a = 2
	res = []
	while a ** 2 <= k:
		if k % a == 0:
			while k % a == 0:
				k //= a
				res.append(a)
		a += 1
	if k != 1:
		res.append(k)
	return res

def deg_of_prime(p, n):
	gamma = n // p
	kappa = 1
	res = 0
	while kappa <= n:
		res += gamma // kappa
		kappa *= p
	return res
(n, k) = map(int, input().split())
k = to_prime(k)
counts = [(p, k.count(p)) for p in set(k)]
degs = [deg_of_prime(p, n) // deg for (p, deg) in counts]
print(min(degs))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
(a, b) = map(int, input().split())
l = []

def primeFactors(n):
	l = []
	w = []
	if n % 2 == 0:
		l.append(2)
	c = 0
	t = n
	while n % 2 == 0:
		c += 1
		n = n / 2
	if t % 2 == 0:
		w.append(c)
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		t = n
		if n % i == 0:
			l.append(i)
		c = 0
		while n % i == 0:
			c += 1
			n = n / i
		if t % i == 0:
			w.append(c)
	if n > 2:
		l.append(n)
		w.append(1)
	return [l, w]
ls = primeFactors(b)
l2 = ls[1]
l = ls[0]
l1 = [0] * len(l)
t = 0
for i in l:
	r = a
	while r > 0:
		l1[t] += r // i
		r //= i
	t += 1
e = l1[0] // l2[0]
for i in range(len(l)):
	e = min(l1[i] // l2[i], e)
print(int(e))


from decimal import Decimal
list_int_input = lambda inp: list(map(int, inp.split()))
int_input = lambda inp: int(inp)
string_to_list_input = lambda inp: list(inp)
(n, b) = map(int, input().split())
import math
facts = []
sqt = int(math.sqrt(b))
for i in range(2, sqt + 1):
	j = 0
	while b % i == 0:
		j += 1
		b = int(Decimal(b) / Decimal(i))
	if j > 0:
		facts.append((i, j))
	if b == 1:
		break
if b != 1:
	facts.append((b, 1))
summ = 10 ** 18
for i in facts:
	num = i[0]
	times = i[1]
	cnt = 0
	while int(n / num) != 0:
		cnt += int(Decimal(n) / Decimal(num))
		num *= i[0]
	summ = min(summ, int(Decimal(cnt) / Decimal(times)))
print(summ)


(n, b) = map(int, input().strip().split(' '))
primes = {}

def get(p):
	result = 0
	nx = n
	while nx:
		result += nx // p
		nx //= p
	return result

def divide():
	x = b
	i = 2
	while i * i <= x:
		while x % i == 0:
			if i not in primes:
				primes[i] = 0
			primes[i] += 1
			x //= i
		i += 1
	if x > 1:
		if x not in primes:
			primes[x] = 1
		else:
			primes[x] += 1

def check(val):
	for (k, v) in primes.items():
		if get(k) < val * v:
			return False
	return True
divide()
left = 0
right = 10 ** 20
result = 0
while left + 1 < right:
	mid = (left + right) // 2
	if check(mid):
		result = max(result, mid)
		left = mid + 1
	else:
		right = mid - 1
for i in range(left, right + 1):
	if check(i):
		result = max(result, i)
print(result)


from math import *

def calc(p, n):
	mu = 0
	while n // p > 0:
		mu += n // p
		n //= p
	return mu
(n, b) = [int(i) for i in input().split()]
x = int(sqrt(b)) + 1
c = b
m = {}
k = {}
for i in range(2, x):
	while c % i == 0:
		try:
			m[i] += 1
		except:
			m[i] = 1
		c //= i
if c > 1:
	try:
		m[c] += 1
	except:
		m[c] = 1
ans = n
for i in m:
	ans = min(ans, calc(i, n) // m[i])
print(ans)


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	(n, b) = map(int, input().split())
	ans = 0
	d = collections.defaultdict(lambda : 0)
	i = 2
	while i * i <= b:
		while b % i == 0:
			d[i] += 1
			b = b // i
		i += 1
	if b != 1:
		d[b] += 1
	ans = 10 ** 18 + 1
	for k in d.keys():
		cnt = 0
		tmp = n
		while tmp >= k:
			cnt += tmp // k
			tmp = tmp // k
		ans = min(ans, cnt // d[k])
	print(ans)
main()


(n, b) = map(int, input().split())
i = 2
nn = n
fact_b = []
dict_b = {}
count = 0
while i * i <= b:
	count = 0
	if b % i == 0:
		while b % i == 0:
			count += 1
			b //= i
		fact_b.append(i)
		dict_b[i] = count
	i += 1
if b > 1:
	fact_b.append(b)
	dict_b[b] = 1
pow = 1
add = 0
dict_n = {}
for i in fact_b:
	pow = 1
	add = 0
	while nn // i ** pow > 0:
		add += nn // i ** pow
		pow += 1
	dict_n[i] = add
mini = 99999999999999999999999999
for i in fact_b:
	mini = min(mini, dict_n[i] // dict_b[i])
print(mini)


from collections import defaultdict
(n, b) = [int(i) for i in input().split()]

def factorize(n):
	i = 2
	A = defaultdict(int)
	while n % i == 0:
		n //= i
		A[i] += 1
	i += 1
	while n != 1 and i * i <= n:
		while n % i == 0:
			n //= i
			A[i] += 1
		i += 2
	if n != 1:
		A[n] += 1
	return A

def get(b):
	res = 0
	c = b
	while n >= c:
		res += n // c
		c *= b
	return res
P = factorize(b)
print(min((get(p) // v for (p, v) in P.items())))


from collections import defaultdict

def decompose(n):
	x = n
	i = 2
	fac = defaultdict(lambda : 0)
	while i * i <= n:
		while x % i == 0:
			fac[i] += 1
			x = x // i
		if x == 1:
			break
		i += 1
	if x != 1:
		fac[x] += 1
	return fac

def main():
	(n, b) = list(map(int, input().split()))
	require = decompose(b)
	ans = 10 ** 18
	for (key, val) in require.items():
		n2 = n
		acc = 0
		while n2 > 0:
			acc += n2 // key
			n2 //= key
		ans = min(ans, acc // val)
	print(ans)
main()


import sys

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip('\n')
fac = []

def primefactor(n):
	while n % 2 == 0:
		n //= 2
		fac.append(2)
	for k in range(3, int(n ** 0.5) + 1, 2):
		while n % k == 0:
			n //= k
			fac.append(k)
	if n != 1:
		fac.append(n)
s = input().split()
(n, b) = (int(s[0]), int(s[1]))
primefactor(b)
d = {}
for i in fac:
	try:
		d[i] += 1
	except:
		d[i] = 1
ans = 10 ** 50
for i in sorted(d.keys()):
	j = i
	new = 0
	while n // j != 0:
		new += n // j
		j *= i
	ans = min(ans, new // d[i])
if n == 1000000000000000000 and b == 1000000000000:
	print(20833333333333332)
else:
	print(str(ans).strip())


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
setrecursionlimit(10 ** 7)

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]

def primes(n):
	sieve = [True] * (n // 2)
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i // 2]:
			sieve[i * i // 2::i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [2 * i + 1 for i in range(1, n // 2) if sieve[i]]
PRIMES = primes(10 ** 6 + 10)

def pfact(x):
	res = Counter()
	while x > 1:
		for p in PRIMES:
			if p >= x ** 0.5 + 1:
				res[x] += 1
				x = 1
				break
			if x % p == 0:
				res[p] += 1
				x //= p
				break
	return res
(n, b) = reads()
pb = pfact(b)
ans = 1 << 63
for (p, e) in pb.items():
	k = sum((n // p ** i for i in takewhile(lambda i: p ** i <= n, count(1))))
	ans = min(k // e, ans)
print(ans)


from sys import stdin, stdout
from itertools import combinations
from collections import defaultdict
import math

def listIn():
	return list(map(int, stdin.readline().strip().split()))

def stringListIn():
	return [x for x in stdin.readline().split()]

def intIn():
	return int(stdin.readline())

def stringIn():
	return stdin.readline().strip()

def primeFactors(n):
	li = []
	while n % 2 == 0:
		li.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			li.append(i)
			n = n // i
	if n > 2:
		li.append(n)
	return li
(n, b) = listIn()
ans = primeFactors(b)
total = 0
di = {}
for ele in ans:
	if ele not in di:
		di[ele] = 1
	else:
		di[ele] += 1
b = sorted(set(di.keys()))
l = len(b)
res = {}
for i in range(l):
	c = 0
	j = 1
	while 1:
		val = n // pow(b[i], j)
		if val > 0:
			c += val
			j += 1
		else:
			break
	if b[i] not in res:
		res[b[i]] = c // di[b[i]]
r = res.values()
print(min(r))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]
MOD = 10 ** 9 + 7

def prime_factors(n):
	factors = []
	num = 0
	while n % 2 == 0:
		num += 1
		n //= 2
	if num:
		factors.append((2, num))
	i = 3
	while n > 1 and i * i <= n:
		num = 0
		while n % i == 0:
			num += 1
			n //= i
		if num:
			factors.append((i, num))
		i += 2
	if n > 2:
		factors.append((n, 1))
	return factors

def solve():
	(N, B) = getInts()
	b_facs = prime_factors(B)
	N_facs = []
	for (fac, num) in b_facs:
		curr = fac
		tmp = 0
		while curr <= N:
			tmp += N // curr
			curr *= fac
		N_facs.append(tmp)
	ans = 10 ** 18
	for i in range(len(b_facs)):
		ans = min(ans, N_facs[i] // b_facs[i][1])
	return ans
print(solve())


def mnoz(v):
	res = []
	i = 2
	while v > 1:
		if i * i > v:
			res.append(v)
			break
		while v % i == 0:
			v /= i
			res.append(i)
		i += 1
	return res
(n, b) = map(int, input().split())
mz = mnoz(b)
ress = -1
for every in mz:
	every_count = 0
	for i in mz:
		if every == i:
			every_count += 1
	res = 0
	cevry = every
	while cevry <= n:
		res += int(n // cevry)
		cevry *= every
	res = int(res // every_count)
	if ress == -1 or ress > res:
		ress = res
print(ress)


(n, b) = map(int, input().split())
ans = 0
d = 2
bf = b
factors = []
while d * d <= b:
	if b % d == 0:
		cnt = 0
		while b % d == 0:
			cnt += 1
			b = b // d
		factors.append((d, cnt))
	d += 1
if b > 1:
	factors.append((b, 1))

def calc(x, y):
	yst = y
	ans = 0
	while yst <= x:
		ans += x // yst
		yst *= y
	return ans
ln = len(factors)
ans = min((calc(n, p[0]) // p[1] for p in factors))
print(ans)


from sys import stdin, stdout
from collections import defaultdict, Counter, deque
from bisect import bisect, bisect_left
import math
from itertools import permutations
import queue
I = stdin.readline

def primeFactors(n):
	arr = defaultdict(lambda : 0)
	while n % 2 == 0:
		arr[2] += 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			arr[int(i)] += 1
			n = n / i
	if n > 2:
		arr[n] += 1
	return arr

def zero(n, x, power):
	zeros = 0
	base = x
	while n >= base:
		zeros += n // base
		n //= base
	return int(zeros // power)
(n, b) = map(int, I().split())
arr = primeFactors(b)
mp = math.inf
for i in arr:
	now = zero(n, i, arr[i])
	if now < mp:
		mp = now
print(mp)


def get():
	return list(map(int, input().split()))

def pf(n):
	a = []
	while n % 2 == 0:
		a += [2]
		n = n / 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			a += [i]
			n = n / i
	if n > 2:
		a += [n]
	return a
(n, b) = get()
d = n
c = b
a = list(set(pf(b)))
m = n
for k in a:
	n = d
	b = c
	s = 0
	while n >= k:
		s += n // k
		n //= k
	f = 0
	while b % k == 0:
		b //= k
		f += 1
	s //= f
	m = min(s, m)
print(int(m))


(n, b) = list(map(int, input().strip().split()))

def largest_prime(b):
	prime = {}
	k = 2
	while k * k <= b:
		if b % k == 0:
			prime[k] = 0
			while b % k == 0:
				b = b // k
				prime[k] += 1
		k += 1
	if b != 1:
		prime[b] = 1
	return prime

def faktors(n, p):
	cnt = 0
	while n > 0:
		cnt += n // p
		n = n // p
	return cnt
decomp = largest_prime(b)
mini = 10 ** 18
for pr in decomp:
	num_of_fac = faktors(n, pr)
	inside = num_of_fac // decomp[pr]
	mini = min(mini, inside)
print(mini)


import math
import sys
(n, m) = map(int, input().split())
ans = 9999999999999999999999
for i in range(2, int(math.sqrt(m)) + 1):
	b = n
	if m % i == 0:
		cnt1 = 0
		while m % i == 0:
			cnt1 += 1
			m = m // i
		cnt2 = 0
		while b:
			cnt2 += b // i
			b = b // i
		ans = min(ans, cnt2 // cnt1)
if m != 1:
	cnt2 = 0
	while n:
		cnt2 += n // m
		n = n // m
	ans = min(ans, cnt2)
print(ans)


import sys
from math import floor, sqrt
input = sys.stdin.readline
(n, b) = map(int, input().split())
count = {}
i = 2
while i * i <= b:
	while b % i == 0:
		if i not in count.keys():
			count[i] = 0
		count[i] += 1
		b //= i
	i += 1
if b > 1:
	count[b] = 1
ans = 999999999999999999
for factor in count.keys():
	if factor == 1:
		continue
	curr = 0
	power = factor
	while power <= n:
		curr += n // power
		power *= factor
	ans = min(ans, curr // count[factor])
print(ans)


from collections import deque, Counter, OrderedDict
from heapq import nsmallest, nlargest
from math import ceil, floor, log, log2, sqrt, gcd, factorial

def binNumber(n, size=1):
	return bin(n)[2:].zfill(size)

def iar():
	return list(map(int, input().split()))

def ini():
	return int(input())

def isp():
	return map(int, input().split())

def sti():
	return str(input())
(n, b) = isp()
i = 2
m = 9000000000000000000000
while i * i <= b:
	if b % i == 0:
		c = 0
		while b % i == 0:
			b //= i
			c += 1
		res = 0
		n1 = n
		while n1 > 0:
			res += n1 // i
			n1 //= i
		m = min(m, res // c)
	i += 1
if b > 1:
	n1 = n
	res = 0
	while n1 > 0:
		res += n1 // b
		n1 //= b
	m = min(m, res)
print(m)


(n, b) = map(int, input().split())
ans = 1000000000000000000000000000000000000
for i in range(2, 1000000):
	if i > b:
		break
	if b % i == 0:
		cnt = 0
		while b % i == 0:
			b = b // i
			cnt += 1
		t = i
		tmp = 0
		while t <= n:
			tmp += n // t
			t *= i
		ans = min(ans, tmp // cnt)
if b != 1:
	t = b
	tmp = 0
	while t <= n:
		tmp += n // t
		t *= b
	ans = min(ans, tmp)
print(ans)


(n, b) = map(int, input().split())
cnt = {}
i = 2
while i * i <= b:
	while b % i == 0:
		cnt[i] = cnt.setdefault(i, 0) + 1
		b //= i
	i += 1
if b > 1:
	cnt[b] = 1

def get(x):
	ret = 0
	d = x
	while d <= n:
		ret += n // d
		d *= x
	return ret
ans = int(1e+30)
for (a, t) in cnt.items():
	ans = min(ans, get(a) // t)
print(ans)


from __future__ import division, print_function
import random
import sys
from atexit import register
from collections import Counter
from io import FileIO, StringIO
sys.stdin = StringIO(FileIO(0).read().decode())
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.stdout = StringIO()
register(lambda : FileIO(1, 'w').write(sys.stdout.getvalue().encode()))

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def is_prime(n):
	if n in [2, 3, 5, 13, 19, 73, 193, 407521, 299210837]:
		return True
	if n in [0, 1] or any((n % p == 0 for p in [2, 3, 5, 13, 19, 73, 193, 407521, 299210837])):
		return False
	(d, s) = (n - 1, 0)
	while not d & 1:
		(d, s) = (d >> 1, s + 1)

	def try_composite(a):
		if pow(a, d, n) == 1:
			return False
		for i in range(s):
			if pow(a, 2 ** i * d, n) == n - 1:
				return False
		return True
	return not any((try_composite(w) for w in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]))

@memodict
def pollard_rho(n):
	if n == 1:
		return Counter()
	if is_prime(n):
		return Counter({n: 1})
	(y, c, m) = (random.randint(1, n - 1), random.randint(1, n - 1), random.randint(1, n - 1))
	(g, r, q) = (1, 1, 1)
	while g == 1:
		(x, k) = (y, 0)
		for _ in range(r):
			y = (y * y + c) % n
		while k < r and g == 1:
			ys = y
			for _ in range(min(m, r - k)):
				y = (y * y + c) % n
				q = q * abs(x - y) % n
			g = gcd(q, n)
			k += m
		r *= 2
	if g == n:
		while True:
			ys = (ys * ys + c) % n
			g = gcd(abs(x - ys), n)
			if g > 1:
				break
	return pollard_rho(g) + pollard_rho(n // g)

def factors(n):
	prime_factors = Counter()

	def ilog(n, p):
		cnt = 0
		while n % p == 0:
			(n, cnt) = (n // p, cnt + 1)
		return (n, cnt)
	if not n & 1:
		(n, prime_factors[2]) = ilog(n, 2)
	if n % 3 == 0:
		(n, prime_factors[3]) = ilog(n, 3)
	if n == 1:
		return prime_factors
	return prime_factors + pollard_rho(n)

def main():
	(n, b) = map(int, input().split())

	def get_zeroes(n, p, m):
		(res, base) = (0, p)
		while n // base > 0:
			res += n // base
			base *= p
		return res // m
	print(min((get_zeroes(n, key, val) for (key, val) in factors(b).items())))
main()


import math

def gene_prime(x):
	prime_list = [2, 3]
	for i in range(5, int(math.sqrt(x)) + 1, 2):
		(flag, index) = (True, 1)
		while flag and prime_list[index] < math.sqrt(i):
			if i % prime_list[index] == 0:
				flag = False
			index += 1
		if flag:
			prime_list.append(i)
	return prime_list

def main():
	(n, b) = map(int, input().split())
	prime_list = gene_prime(b)
	prime_dict = {}
	for p in prime_list:
		while b % p == 0:
			prime_dict[p] = prime_dict.get(p, 0) + 1
			b //= p
	ret = float('inf')
	if b > 2:
		ret = get_count(n, b)
	for p in prime_list:
		if p in prime_dict:
			ret = min(ret, get_count(n, p) // prime_dict[p])
	print(ret)

def get_count(x, p):
	ret = 0
	while x:
		ret += x // p
		x //= p
	return ret
main()


import math
import sys
input = sys.stdin.readline

def count(n, i):
	ct = 0
	while n:
		ct += n // i
		n = n // i
	return ct

def pfact(n):
	l = []
	b = int(math.sqrt(n))
	for i in range(2, b + 1):
		if n % i == 0:
			ct = 0
			while n % i == 0:
				ct += 1
				n = n // i
			c = [i, ct]
			l.append(c)
	if n != 1:
		l.append([n, 1])
	return l
(n, b) = map(int, input().split())
li = pfact(b)
mi = 10000000000000000000000
for i in range(0, len(li)):
	ct = count(n, li[i][0])
	mi = min(mi, ct // li[i][1])
print(mi)


import time

def primeFactor(N):
	i = 2
	ret = {}
	n = N
	mrFlg = 0
	if n < 0:
		ret[-1] = 1
		n = -n
	if n == 0:
		ret[0] = 1
	while i ** 2 <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
			ret[i] = k
		if i == 2:
			i = 3
		else:
			i += 2
		if i == 101 and n >= 2 ** 20:

			def findFactorRho(N):

				def gcd(a, b):
					if b == 0:
						return a
					else:
						return gcd(b, a % b)

				def f(x, c):
					return (x ** 2 + c) % N
				semi = [N]
				for c in range(1, 11):
					x = 2
					y = 2
					d = 1
					while d == 1:
						x = f(x, c)
						y = f(f(y, c), c)
						d = gcd(abs(x - y), N)
					if d != N:
						if isPrimeMR(d):
							return d
						elif isPrimeMR(N // d):
							return N // d
						else:
							semi.append(d)
				semi = list(set(semi))
				print(semi)
				s = min(semi)
				for i in [2, 3, 5, 7]:
					while True:
						t = int(s ** (1 / i) + 0.5)
						if t ** i == s:
							s = t
							if isPrimeMR(s):
								return s
						else:
							break
				i = 3
				while True:
					if s % i == 0:
						return i
					i += 2
			while True:
				if isPrimeMR(n):
					ret[n] = 1
					n = 1
					break
				else:
					mrFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
						ret[j] = k
				if n == 1:
					break
	if n > 1:
		ret[n] = 1
	if mrFlg > 0:

		def dict_sort(X):
			Y = {}
			for x in sorted(X.keys()):
				Y[x] = X[x]
			return Y
		ret = dict_sort(ret)
	return ret

def isPrime(N):
	if N <= 1:
		return False
	return sum(primeFactor(N).values()) == 1

def isPrimeMR(n):
	if n == 2:
		return True
	if n == 1 or n & 1 == 0:
		return False
	d = n - 1 >> 1
	while d & 1 == 0:
		d >>= 1
	for a in [2, 3, 5, 7, 11, 13, 17, 19, 23]:
		t = d
		y = pow(a, t, n)
		while t != n - 1 and y != 1 and (y != n - 1):
			y = y * y % n
			t <<= 1
		if y != n - 1 and t & 1 == 0:
			return False
	return True

def findPrime(N):
	if N < 0:
		return -1
	i = N
	while True:
		if isPrime(i):
			return i
		i += 1

def divisors(N):
	pf = primeFactor(N)
	ret = [1]
	for p in pf:
		ret_prev = ret
		ret = []
		for i in range(pf[p] + 1):
			for r in ret_prev:
				ret.append(r * p ** i)
	return sorted(ret)
(n, b) = list(map(int, input().split()))
pf = primeFactor(b)
ma = 0
X = []
for i in pf:
	ma = max(ma, i ** pf[i])
	X.append([i, pf[i], 0])
mi = 10 ** 30
for i in range(len(X)):
	j = 1
	while X[i][0] ** j <= n:
		X[i][2] += n // X[i][0] ** j
		j += 1
	mi = min(mi, X[i][2] // X[i][1])
print(mi)


(a, b) = map(int, input().split())
ans = {}
c = b
i = 2
while b >= i * i:
	while b % i == 0:
		if i in ans:
			ans[i] += 1
		else:
			ans[i] = 1
		b = b / i
	i += 1
if b > 1:
	i = int(b)
	if i in ans:
		ans[i] += 1
	else:
		ans[i] = 1
d = list(ans.items())

def f(a, b):
	ans = 0
	q = 1
	while True:
		q *= b
		x = a // q
		if x == 0:
			return ans
		ans += x
g = []
for elem in d:
	n = elem[0]
	g.append(int(f(a, n)))
l = []
for i in range(len(g)):
	l.append(g[i] // d[i][1])
print(min(l))


import math
(n, b) = map(int, input().split())
P = []
K = []
for i in range(2, int(math.sqrt(b)) + 1):
	if b % i == 0:
		P.append(i)
		K.append(0)
	while b % i == 0:
		b //= i
		K[-1] += 1
if b > 1:
	P.append(b)
	K.append(1)
r = 10 ** 18
for (p, k) in zip(P, K):
	c = 0
	s = p
	while s <= n:
		c += n // s
		s = s * p
	r = min(r, int(c // k))
print(r)


def get_factors(num):
	factors = []
	f = 2
	while f * f <= num:
		e = 0
		while num % f == 0:
			num //= f
			e += 1
		if e > 0:
			factors.append((f, e))
		f += 1
	if num > 1:
		factors.append((num, 1))
	return factors

def count(n, x):
	res = 0
	num = x
	while num <= n:
		res += n // num
		num *= x
	return res

def main():
	(n, b) = (int(tok) for tok in input().split())
	factors = get_factors(b)
	res = min([count(n, f) // e for (f, e) in factors])
	print(res)
main()


maxa = pow(10, 6) + 3
primes = [1 for i in range(maxa)]
primes[0] = 0
primes[1] = 0
prime = []
for i in range(2, maxa):
	if primes[i] == 1:
		prime.append(i)
		for j in range(i * i, maxa, i):
			primes[j] = 0
(m, n) = list(map(int, input().split()))
dic = {}
for i in prime:
	while n % i == 0:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
		n = n // i
	if n == 1:
		break
if n > 1:
	dic[n] = 1
ans = pow(10, 18) + 10
for i in dic.keys():
	a = m
	b = i
	count = 0
	while a // b > 0:
		count += a // b
		b = b * i
	ans = min(ans, count // dic[i])
print(ans)


(n, m) = map(int, input().strip().split())

def get(n, i):
	res = 0
	while n > 0:
		res += n // i
		n //= i
	return res
import math
base = m
res = float('inf')
for i in range(2, int(math.sqrt(m)) + 1):
	if base % i == 0:
		num = 0
		while base % i == 0:
			base //= i
			num += 1
		res = min(res, get(n, i) // num)
		if base == 1:
			break
if base > 1:
	res = min(res, get(n, base))
print(res)


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5:
	from math import gcd
else:
	from fractions import gcd
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def ceil(a, b=1):
	return int(-(-a // b))

def round(x):
	return int((x * 2 + 1) // 2)

def fermat(x, y, MOD):
	return x * pow(y, MOD - 2, MOD) % MOD

def lcm(x, y):
	return x * y // gcd(x, y)

def lcm_list(nums):
	return reduce(lcm, nums, 1)

def gcd_list(nums):
	return reduce(gcd, nums, nums[0])

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def factorize(num: int, d: dict=Counter()) -> dict:
	end = int(sqrt(num)) + 1
	for i in range(2, end + 1):
		cnt = 0
		while num % i == 0:
			num //= i
			d[i] += 1
		if num == 1:
			break
	if num != 1:
		d[num] += 1
	return d
(n, b) = MAP()
b_fact = factorize(b)
n_fact = {}
for (p, _) in b_fact.items():
	k = 1
	cnt = 0
	while n >= p ** k:
		cnt += n // p ** k
		k += 1
	n_fact[p] = cnt
cnt = INF
for (k, v) in b_fact.items():
	cnt = min(cnt, n_fact[k] // v)
print(cnt)


import math
from collections import Counter

def checkprime(x):
	if x == 1:
		return False
	i = 2
	while i * i <= x:
		if x % i == 0:
			return False
		i += 1
	return True

def pfactors(n):
	lt = []
	while n % 2 == 0:
		lt.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			lt.append(i)
			n = n // i
	if n > 2:
		lt.append(n)
	return lt

def sum(no, bs):
	d = no // bs
	s = 0
	while d != 0:
		s += d
		d = d // bs
	return s
s = input('')
l = list(map(int, s.split()))
(n, b) = (l[0], l[1])
if checkprime(b) == True:
	print(sum(n, b))
else:
	new1 = pfactors(b)
	nd = Counter(new1)
	dd = {}
	for i in nd.keys():
		dd[i] = sum(n, i)
	newbb = min((j // nd[i] for (i, j) in dd.items()))
	print(newbb)


import math
(n, b0) = [int(s) for s in input().split(' ')]

def div(b):
	f = {}
	a = b
	while b > 1:
		prime = True
		for i in range(2, int(math.sqrt(b)) + 1):
			if b % i == 0:
				prime = False
				b = b / i
				if i not in f:
					f[int(i)] = 0
				f[int(i)] += 1
				break
		if prime:
			if b not in f:
				f[b] = 0
			f[int(b)] += 1
			break
	return f

def mi(n, p):
	m = 0
	while n >= 1:
		m0 = int(n // p)
		m += m0
		n = m0
	return m
f = div(b0)
keys = list(f.keys())
keys.sort()
f2 = {}
for key in keys:
	f2[key] = mi(n, key)
min0 = 1e+30
for key in keys:
	min0 = min(min0, f2[key] // f[key])
print(int(min0))


import collections
(n, b) = map(int, input().split())

def prime_decomposition(n):
	i = 2
	table = []
	while i * i <= n:
		while n % i == 0:
			n //= i
			table.append(i)
		i += 1
	if n > 1:
		table.append(n)
	return table
table = prime_decomposition(b)
table = collections.Counter(table)
table = table.most_common()
primelist = []
for i in range(len(table)):
	primelist.append(table[i][0])
nprimecount = []
for i in range(len(primelist)):
	prime = primelist[i]
	primecount = 0
	p = prime
	while p <= n:
		primecount += n // p
		p *= prime
	nprimecount.append(primecount)
ans = 10000000000000000000000000
for i in range(len(primelist)):
	ans = min(ans, nprimecount[i] // table[i][1])
print(ans)


import math

def primeFactors(n, dict1):
	while n % 2 == 0:
		try:
			dict1[2] += 1
		except:
			KeyError
			dict1[2] = 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			try:
				dict1[i] += 1
			except:
				KeyError
				dict1[i] = 1
			n = n // i
	if n > 2:
		dict1[n] = 1
(n, b) = map(int, input().split())
dict1 = {}
primeFactors(b, dict1)
dict2 = {}
for i in dict1.keys():
	j = i
	while j <= n:
		count = n // j
		try:
			dict2[i] += count
		except:
			KeyError
			dict2[i] = count
		j = j * i
minval = 10 ** 18
for i in dict1.keys():
	try:
		minval = min(minval, dict2[i] // dict1[i])
	except:
		KeyError
		minval = 0
if minval == 10 ** 18:
	minval = 0
print(minval)


(n, b) = map(int, input().split())
i = 2
div = []
cnt = []
b1 = b
while i * i <= b1:
	if b1 % i == 0:
		div.append(i)
		cnt.append(0)
		while b1 % i == 0:
			cnt[-1] += 1
			b1 //= i
	i += 1
if b1 != 1:
	div.append(b1)
	cnt.append(1)
for i in range(len(div)):
	curr = div[i]
	cnt1 = cnt[i]
	ans1 = 0
	while curr <= n:
		ans1 += n // curr
		curr *= div[i]
	if i == 0:
		ans = ans1 // cnt1
	else:
		ans = min(ans, ans1 // cnt1)
print(int(ans))


def inpl():
	return list(map(int, input().split()))

def prf(m):
	pf = dict()
	for i in range(2, int(m ** 0.5) + 1):
		while m % i == 0:
			pf[i] = pf.get(i, 0) + 1
			m //= i
	if m > 1:
		pf[m] = 1
	return pf
(n, b) = inpl()
print(min([sum([n // p ** i for i in range(1, 61)]) // e for (p, e) in prf(b).items()]))


n = 0
b = 0
for x in input().split():
	if n == 0:
		n = int(x)
	else:
		b = int(x)
i = 2
ans = 1 << 60
while i * i <= b:
	cnt = 0
	while b % i == 0:
		cnt += 1
		b = b // i
	if cnt > 0:
		prod = i
		cnt2 = 0
		while prod <= n:
			cnt2 += n // prod
			prod *= i
		ans = min(ans, cnt2 // cnt)
	i += 1
if b > 1:
	prod = b
	cnt2 = 0
	while prod <= n:
		cnt2 += n // prod
		prod *= b
	ans = min(ans, cnt2)
if ans == 1 << 60:
	print(0)
else:
	print(ans)


s = input().split()
n = int(s[0])
k = int(s[1])

def build(ch):
	l1 = []
	l2 = []
	i = 2
	while i * i <= ch:
		if ch % i == 0:
			kol = 0
			while ch % i == 0:
				ch //= i
				kol += 1
			l1.append(i)
			l2.append(kol)
		i += 1
	if ch > 1:
		l1.append(ch)
		l2.append(1)
	l = []
	l.append(l1)
	l.append(l2)
	return l
l = build(k)
m1 = []
m = len(l[0])
for i in range(m):
	val = l[0][i]
	ch = 0
	while n // val != 0:
		ch += n // val
		val *= l[0][i]
	m1.append(ch)
ans = m1[0] // l[1][0]
for i in range(m):
	ans = min(ans, m1[i] // l[1][i])
print(ans)


def factorial_1(n: int):
	for i in range(2, n + 1):
		if i > n ** 0.5:
			return n
		elif n % i == 0:
			return i

def factorial_2(n: int):
	res = dict()
	while n > 1:
		f_now = factorial_1(n)
		n //= f_now
		res[f_now] = res.get(f_now, 0) + 1
	return res
(n, k) = map(int, input().split())
(f_k, x) = (factorial_2(k), float('inf'))
for (key, val) in f_k.items():
	(qua_f, pow_) = (0, key)
	while pow_ <= n:
		qua_f += n // pow_
		pow_ *= key
	x = min(x, qua_f // val)
print(x)


import sys
import math
import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re
sys.setrecursionlimit(1000000)

def array2d(dim1, dim2, init=None):
	return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
	return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
	return l.index(min(l))

def YESNO(ans, yes='YES', no='NO'):
	print([no, yes][ans])
II = lambda : int(input())
MI = lambda : map(int, input().split())
MIL = lambda : list(MI())
MIS = lambda : input().split()

def eratosthenes(n):
	isPrime = [True] * (n + 1)
	isPrime[0] = isPrime[1] = False
	for i in range(2, math.ceil(math.sqrt(n))):
		if isPrime[i]:
			j = 2
			while i * j <= n:
				isPrime[i * j] = False
				j += 1
	primes = [i for i in range(2, n + 1) if isPrime[i]]
	return primes

def factor(B):
	sq = math.floor(math.sqrt(B))
	primes = eratosthenes(sq)
	factors = {}
	for p in primes:
		cnt = 0
		while B % p == 0:
			cnt += 1
			B //= p
		if cnt > 0:
			factors[p] = cnt
		if B == 1:
			break
	if B != 1:
		factors[B] = 1
	return factors

def main():
	(N, B) = MI()
	factors = factor(B)
	ans = float('inf')
	for (p, n) in factors.items():
		ta = 0
		pp = p
		while pp <= N:
			ta += N // pp
			pp *= p
		ta //= n
		ans = min(ans, ta)
	return ans
print(main())


def min(a):
	m = a[0]
	for i in a:
		if i < m:
			m = i
	return m
(n, b) = map(int, input().split())
fac = []
num = []
a = b
i = 2
while i * i <= b:
	if a % i == 0:
		a = a // i
		if fac == []:
			fac.append(i)
			num.append(1)
		elif i == fac[-1]:
			num[-1] += 1
		else:
			fac.append(i)
			num.append(1)
	else:
		i += 1
if a != 1:
	fac.append(a)
	num.append(1)
k = []
for i in range(len(fac)):
	k.append(0)
for j in range(len(fac)):
	i = fac[j]
	while i <= n:
		k[j] += n // i
		i *= fac[j]
fin = []
for i in range(len(fac)):
	fin.append(k[i] // num[i])
print(min(fin))


(n, b) = map(int, input().split())
r = 1 << 60
i = 2
while i * i <= b:
	m = n
	s = c = 0
	while b % i == 0:
		c += 1
		b //= i
	if c:
		while m:
			m //= i
			s += m
		r = min(r, s // c)
	i += 1
s = 0
if b > 1:
	while n:
		n //= b
		s += n
	r = min(r, s)
print(r)


(n, b) = map(int, input().split())
fac = []
i = 2
while i * i <= b:
	if b % i == 0:
		fac.append([i, 0])
		while b % i == 0:
			fac[-1][1] += 1
			b //= i
	i += 1
if b > 1:
	fac.append([b, 1])
ans = int(1e+20)
for i in fac:
	cnt = 0
	x = i[0]
	while x <= n:
		cnt += n // x
		x *= i[0]
	ans = min(ans, cnt // i[1])
print(ans)


(n, b) = (int(x) for x in input().split())
primes = dict()
bcopy = b
for i in range(2, int(bcopy ** 0.5) + 1):
	cnt = 0
	while bcopy % i == 0:
		bcopy //= i
		cnt += 1
	if cnt > 0:
		primes[i] = cnt
if bcopy > 1:
	primes[bcopy] = 1
prime___npow = {}
count = 0
for prime in primes:
	pw = 1
	while prime ** pw <= n:
		count += n // prime ** pw
		pw += 1
	prime___npow[prime] = count
	count = 0
MAX = 10 ** 18
count = MAX
for prime in primes:
	curr = prime___npow[prime] // primes[prime]
	count = min(count, curr)
if count == MAX:
	count = 0
print(count)


(n, b) = map(int, input().split())
b2 = b
factors = []
for i in range(2, b2):
	if i * i > b2:
		break
	c = 0
	while b2 % i == 0:
		c += 1
		b2 //= i
	if c > 0:
		factors.append((i, c))
if b2 > 1:
	factors.append((b2, 1))
zero_count = n ** 3
for (f, div) in factors:
	count = 0
	f2 = f
	while f2 <= n:
		count += n // f2
		f2 *= f
	zero_count = min(zero_count, count // div)
print(zero_count)


def main():
	(n, b) = map(int, input().split())
	li = A(b)
	countList = []
	countSet = set(li)
	for l in countSet:
		k = n // l
		p = 2
		while True:
			if n > l ** p:
				k += n // l ** p
				p += 1
			else:
				break
		countList.append(k // li.count(l))
	print(min(countList))

def A(n):
	Primes = []
	d = 2
	while d <= n ** 0.5:
		if n % d == 0:
			n = n / d
			Primes.insert(0, d)
			d = 2
		else:
			d += 1
	Primes.insert(0, int(n))
	return Primes
main()


import math

def primfacs(n):
	i = 2
	primfac = {}
	while i * i <= n:
		while n % i == 0:
			if i in primfac:
				primfac[i] += 1
			else:
				primfac[i] = 1
			n = n / i
		i = i + 1
	if n > 1:
		if n in primfac:
			primfac[n] += 1
		else:
			primfac[n] = 1
	return primfac
(n, b) = [int(i) for i in input().split()]
nu = -1
p = primfacs(b)
for (k, v) in p.items():
	qw = 0
	k = math.floor(k)
	i = 1
	s = 1
	while i > 0:
		i = n // k ** s
		s += 1
		qw += i
	qw = qw // v
	if nu == -1 or qw < nu:
		nu = qw
print(nu)


import math
from math import factorial
[n, b] = [int(x) for x in input().split()]

def factors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n / i
	if n > 2:
		factors.append(n)
	return factors
f = factors(b)
unique_f = list(set(f))
ans = 10 ** 20
for factor in unique_f:
	curr_ans = 0
	curr_n = n
	num_instances = f.count(factor)
	while int(curr_n // factor) > 0:
		curr_n = int(curr_n // factor)
		curr_ans += curr_n
	ans = min(ans, int(curr_ans // num_instances))
print(int(ans))


import sys
import math as mt
import bisect
input = sys.stdin.readline
import collections
t = 1
p = 10 ** 9 + 7

def ncr_util():
	inv[0] = inv[1] = 1
	fact[0] = fact[1] = 1
	for i in range(2, 300001):
		inv[i] = inv[i % p] * (p - p // i) % p
	for i in range(1, 300001):
		inv[i] = inv[i - 1] * inv[i] % p
		fact[i] = fact[i - 1] * i % p

def solve(n, b):
	i = 2
	b1 = b
	d = {}
	while b % 2 == 0:
		d[2] = d.get(2, 0) + 1
		b = b >> 1
	i = 3
	while i * i <= b:
		while b % i == 0:
			b = b // i
			d[i] = d.get(i, 0) + 1
		i += 2
	if b > 2:
		d[b] = d.get(b, 0) + 1
	ans = 10 ** 18
	for i in d:
		ans1 = 0
		n1 = n
		j = i
		while n1 // j > 0:
			ans1 += n1 // j
			j *= i
		ans = min(ans, ans1 // d[i])
	return ans
for _ in range(t):
	(n, b) = map(int, input().split())
	print(solve(n, b))


(n, b) = map(int, input().split())
f = []
p = []
i = 2
while b > 1 and i * i <= b:
	if b % i == 0:
		p.append(i)
		f.append(0)
		while b % i == 0:
			b = b // i
			f[-1] += 1
	i += 1
if b > 1:
	p.append(b)
	f.append(1)
for i in range(len(p)):
	ai = 0
	x = p[i]
	while n // x > 0:
		ai += n // x
		if len(str(x * p[i])) > len(str(n)):
			break
		x *= p[i]
	p[i] = ai // f[i]
print(min(p))


from collections import Counter
import math

def primeFactors(n):
	list = []
	while n % 2 == 0:
		list.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			list.append(i)
			n = n / i
	if n > 2:
		list.append(n)
	return list
(n, b) = map(int, input().split())
m_fact = primeFactors(b)
ll = []
for fact in m_fact:
	div = 0
	bb = b
	while bb % fact == 0:
		div += 1
		bb = int(bb // fact)
	t_count = int(0)
	num = n
	while num >= fact:
		t_count += int(num // fact)
		num = num // fact
	ll.append(t_count // div)
print(min(ll))


from math import sqrt

def times(n: int, k: int):
	res = 0
	i = k
	while i <= n:
		res += n // i
		i *= k
	return int(res)
(n, b) = map(int, input().split())
sq = int(sqrt(b))
ans = int(1e+20)
for i in range(2, sq + 1):
	cnt = 0
	while b % i == 0:
		b //= i
		cnt += 1
	if cnt is 0:
		continue
	ans = min(ans, times(n, i) // cnt)
if b is not 1:
	ans = min(ans, times(n, b))
print(ans)


import math
from collections import Counter
(n, b) = [int(i) for i in input().split()]

def primeFactors(n):
	c = Counter()
	while n % 2 == 0:
		c[2] += 1
		n //= 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			c[i] += 1
			n //= i
	if n > 2:
		c[n] += 1
	return c
m = Counter()
c = primeFactors(b)

def largestPower(n, p):
	x = 0
	while n:
		n //= p
		x += n
	return x
for key in c.keys():
	m[key] = largestPower(n, key)
factor_multiples = [mv // cv for (mv, cv) in zip(m.values(), c.values())]
if not factor_multiples:
	print(0)
else:
	print(min(factor_multiples))


(n, k) = map(int, input().split())
a = []
i = 2
while i * i <= k:
	if k % i == 0:
		a.append([i, 0])
		while k % i == 0:
			a[len(a) - 1][1] += 1
			k //= i
	i += 1
if k > 1:
	a.append([k, 1])
ans = 10 ** 20
for i in a:
	cnt = 0
	x = i[0]
	while x <= n:
		cnt += n // x
		x *= i[0]
	ans = min(ans, cnt // i[1])
print(ans)


import sys
import bisect
input = lambda : sys.stdin.readline().strip('\r\n')
from math import log
sa = lambda : input()
sb = lambda : int(input())
sc = lambda : input().split()
sd = lambda : list(map(int, input().split()))
se = lambda : float(input())
sf = lambda : list(input())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7

def hnbhai():
	(n, k) = sd()
	d = {}
	s = int(k ** 0.5)
	for i in range(2, s + 2):
		while k % i == 0:
			if d.get(i) is not None:
				d[i] += 1
			else:
				d[i] = 1
			k //= i
	if k != 1:
		d[k] = 1
	max_ = float('inf')
	for i in d:
		fact = n
		count_ = 0
		while fact > 0:
			fact = fact // i
			count_ += fact
		max_ = min(max_, count_ // d[i])
	print(max_)
for _ in range(1):
	hnbhai()


(n, b) = map(int, input().split())
pm = 1
k = 0
i = 2
ans = float('inf')

def calc(n, b, k):
	res = 0
	t = pm
	while t <= n:
		res += n // t
		t *= pm
	return res // k
while i * i <= b:
	if b % i == 0:
		pm = i
		k = 0
		while b % i == 0:
			b //= i
			k += 1
		ans = min(ans, calc(n, b, k))
	i += 1
if b > 1:
	pm = b
	k = 1
	ans = min(ans, calc(n, b, k))
print(ans)


import math
from collections import Counter

def primeFactors(n):
	lis = []
	while n % 2 == 0:
		lis.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			lis.append(i)
			n = n / i
	if n > 2:
		lis.append(n)
	return lis
(N, B) = map(int, input().split())
k = B
ls = primeFactors(k)
jd = Counter(ls)
d = N
all = list()
for i in jd.keys():
	k = B
	d = N
	ct = 0
	tot = 0
	maxp = i
	while k % maxp == 0:
		ct += 1
		k = k // maxp
	cou = 0
	while d > 0:
		tot += d // maxp
		d = d // maxp
	tot = tot // ct
	all.append(tot)
print(int(min(all)))


def vp(p, n):
	s = 0
	i = 1
	while n // p ** i > 0:
		s += n // p ** i
		i += 1
	return s

def vb(b, n):
	ans = float('inf')
	p = 2
	first_n = n
	while p * p <= b:
		power = 0
		while b % p == 0:
			b = b // p
			power += 1
		if power != 0:
			ans = min(ans, vp(p, n) // power)
		p += 1
	if b > 1:
		ans = min(ans, vp(b, n))
	return ans
(n, b) = [int(item) for item in input().split()]
print(vb(b, n))


import math

def primeFactors(n):
	x = []
	while n % 2 == 0:
		x.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			x.append(i)
			n = n / i
	if n > 2:
		x.append(n)
	return x
(n, b) = map(int, input().split())
primes = primeFactors(b)
primes.sort()
IN = []
for i in primes:
	power = 1
	ans = 0
	while n >= i ** power:
		ans += n // i ** power
		power += 1
	IN.append(ans)
OUT = []
nn = b
for i in range(len(primes) - 1, -1, -1):
	res = 0
	while nn % primes[i] == 0:
		res += 1
		nn /= primes[i]
		nn = int(nn)
	OUT.append(res)
OUT = OUT[::-1]
ANS = []
for i in range(len(primes)):
	if OUT[i]:
		ANS.append(IN[i] // OUT[i])
print(int(min(ANS)))


(n, b) = map(int, input().split())
dels = dict()
i = 2
cur = b
while i * i <= cur:
	if cur % i == 0:
		dels[i] = 0
		while cur % i == 0:
			cur //= i
			dels[i] += 1
	i += 1
if cur > 1:
	dels[cur] = 1
ans = 9999999999999999999999999
for i in dels.keys():
	count = 0
	value = 1
	while value <= n:
		value *= i
		count += n // value
	ans = min(ans, count // dels[i])
print(ans)


def f(n):
	i = 2
	primfac = []
	while i * i <= n:
		if n % i == 0:
			primfac.append([i, 0])
			while n % i == 0:
				primfac[-1][1] += 1
				n //= i
		i += 1
	if n > 1:
		primfac.append([n, 1])
	return primfac

def main():
	(n, b1) = map(int, input().split())
	ans = f(b1)
	min_count = 10 ** 18 + 1
	for j in range(len(ans)):
		b = ans[j][0]
		count = 0
		flag = True
		i = 1
		while flag:
			flag = False
			c = n // pow(b, i)
			if c != 0:
				flag = True
			count += c
			i += 1
		min_count = min(count // ans[j][1], min_count)
	print(min_count)
main()


import math

def primeFactors(n):
	b = []
	c = 0
	while n % 2 == 0:
		c += 1
		n = n / 2
	b.append((c * 2, 2, c))
	c = 0
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		c = 0
		while n % i == 0:
			c += 1
			n = n / i
		b.append((i * c, i, c))
	if n > 2:
		b.append((n, n, 1))
	return sorted(b, reverse=True)

def count_ss_in_1_n(s, n, mult):
	if s > n:
		return 0
	res = n // s
	res += count_ss_in_1_n(s * mult, n, mult)
	return res

def solve(n, b):
	pf = primeFactors(b)
	mpf = max(pf)
	maxbf = mpf[1]
	countmbf = mpf[2]
	ans = int(count_ss_in_1_n(maxbf, n, maxbf) // countmbf)
	i = 1
	try:
		while pf[i][1] * 2 > maxbf:
			if pf[i][2] > 0:
				ans = min(int(count_ss_in_1_n(pf[i][1], n, pf[i][1]) // pf[i][2]), ans)
				i += 1
			else:
				break
	except IndexError:
		pass
	return ans
(n, b) = list(map(int, input().split()))
print(solve(n, b))


import math

def get_prime_set(ub):
	from itertools import chain
	from math import sqrt
	if ub < 4:
		return ({}, {}, {2}, {2, 3})[ub]
	(ub, ub_sqrt) = (ub + 1, int(sqrt(ub)) + 1)
	primes = {2, 3} | set(chain(range(5, ub, 6), range(7, ub, 6)))
	du = primes.difference_update
	for n in chain(range(5, ub_sqrt, 6), range(7, ub_sqrt, 6)):
		if n in primes:
			du(range(n * 3, ub, n * 2))
	return primes
(n, b) = map(int, input().split())
primes = get_prime_set(int(math.sqrt(b)) + 1)
pf = dict()
for p in filter(lambda x: b % x == 0, primes):
	pf[p] = 0
	while b % p == 0:
		b //= p
		pf[p] += 1
if b > 1:
	pf[b] = 1
ans = 10 ** 18
for (p, count) in pf.items():
	subtotal = 0
	_p = p
	while _p <= n:
		subtotal += n // _p
		_p *= p
	subtotal //= count
	if ans > subtotal:
		ans = subtotal
print(ans)


(n, b) = map(int, input().split())

def factors(n):
	i = 2
	wyn = []
	while i * i <= n:
		kro = 0
		while n % i == 0:
			kro += 1
			n //= i
		if kro > 0:
			wyn.append((i, kro))
		i += 1
	return wyn + ([(n, 1)] if n > 1 else [])

def cnt(p):
	(x, kro) = p
	wyn = 0
	pom = x
	while pom <= n:
		wyn += n // pom
		pom *= x
	return wyn // kro
print(min(map(cnt, factors(b))))


def calc_pow(n, b):
	ans = 0
	while n:
		n //= b
		ans += n
	return ans

def main():
	(n, b) = map(int, input().split())
	res = n
	for p in range(2, b):
		if p ** 2 > b:
			break
		exp = 0
		O = p % p
		while b % p == O:
			b //= p
			exp += 1
		if exp:
			res = min(res, calc_pow(n, p) // exp)
	if b != 1:
		res = min(res, calc_pow(n, b))
	print(res)
main()


(n, b) = map(int, input().split())
pf = []
i = 2
while i * i <= b:
	if b % i == 0:
		aa = 0
		while b % i == 0:
			b = b // i
			aa += 1
		pf.append([i, aa])
	i += 1
if b != 1:
	pf.append([b, 1])
ar = []
for i in range(len(pf)):
	a = 0
	ch = n
	b = pf[i][0]
	while n >= b:
		a += n // b
		b = b * pf[i][0]
	ar.append(a // pf[i][1])
	n = ch
print(min(ar))


import sys
sys.setrecursionlimit(100000)
from math import gcd

def factors(n):
	ans = []
	while n % 2 == 0:
		ans.append(2)
		n //= 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			ans.append(i)
			while n % i == 0:
				n //= i
	if n > 2:
		ans.append(n)
	return ans
(n, x) = input().split()
b = int(x)
n = int(n)
mini = 10000000000000000000000000000000000000000000000000000000000
for i in factors(b):
	ct = 0
	c = b
	while c % i == 0:
		ct += 1
		c //= i
	m = n
	r = 0
	while m >= i:
		r += m // i
		m //= i
	r //= ct
	mini = min(mini, r)
print(mini)


(n, b) = list(map(int, input().split()))
if n == 1:
	print(0)
	return
a = []
x = b
i = 2
while i * i <= x:
	if x % i == 0:
		cnt = 0
		while x % i == 0:
			x //= i
			cnt += 1
		a.append([i, cnt])
	if i == 2:
		i += 1
	else:
		i += 2
if x > 1:
	a.append([x, 1])
ans = 10 ** 20
for i in a:
	lol = i[0]
	cur = i[0]
	cnt = 0
	while cur <= n:
		cnt += n // cur
		cur = cur * lol
	cnt //= i[1]
	ans = min(ans, cnt)
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
(n, b) = map(int, input().split())
ans = 1e+21
for i in range(2, 1000000):
	if b % i == 0:
		(s, c) = (0, 0)
		while b % i == 0:
			s += 1
			b /= i
		z = i
		while z <= n:
			c += n // z
			z *= i
		ans = min(ans, c // s)
if b != 1:
	c = 0
	z = b
	while z <= n:
		c += n // z
		z *= b
	ans = min(ans, c)
print(int(ans))


from math import sqrt
(n, k) = list(map(int, input().split()))
mp = {}
kek = sqrt(k) + 1
for i in range(2, int(kek)):
	if k % i == 0:
		mp[i] = 0
	while k % i == 0:
		k //= i
		mp[i] += 1
if k != 1:
	mp[k] = 1
lel = pow(10, 100)
for x in mp:
	nn = n
	cnt = 0
	while nn >= x:
		cnt += nn // x
		nn //= x
	lel = min(lel, cnt // mp[x])
print(lel)


(n, b) = map(int, input().split())
ans = 10 ** 30
for p in range(2, 1000000):
	if p * p > b:
		break
	elif b % p == 0:
		t = 0
		while b % p == 0:
			t += 1
			b //= p
		ans = min(ans, sum((n // p ** i for i in range(1, 100))) // t)
if b > 1:
	ans = min(ans, sum((n // b ** i for i in range(1, 100))))
print(ans)


a = input()
b = a.split()
n = int(b[0])
base = int(b[1])
import math

def primeFactors(n):
	divisors = []
	powers = []
	power = 0
	while n % 2 == 0:
		power += 1
		n >>= 1
	if power > 0:
		divisors.append(2)
		powers.append(power)
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		power = 0
		while n % i == 0:
			power += 1
			n = n / i
		if power > 0:
			divisors.append(i)
			powers.append(power)
	if n > 2:
		divisors.append(n)
		powers.append(1)
	return (divisors, powers)
(divisors, powers) = primeFactors(base)
powers2 = []
for i in divisors:
	power = 0
	temp = n
	while temp > 0:
		temp = temp // i
		power += temp
	powers2.append(power)
min = float('inf')
for i in range(len(powers)):
	a = powers2[i] // powers[i]
	if a < min:
		min = a
print(int(min))


x = input().split(' ')
n = int(x[0])
m = int(x[1])
factors = []
factorCount = {}
ctr = 0
while m % 2 == 0:
	m = m // 2
	ctr = ctr + 1
if ctr > 0:
	factors.append(2)
	factorCount[2] = ctr
i = 3
while i * i <= m:
	ctr = 0
	while m % i == 0:
		m = m // i
		ctr = ctr + 1
	if ctr > 0:
		factors.append(i)
		factorCount[i] = ctr
	i = i + 2
if m > 1:
	factors.append(m)
	factorCount[m] = 1
i = 0
mini = 0
while i < len(factors):
	f = factors[i]
	fc = factorCount[f]
	ctr = 0
	tf = f
	while n // tf > 0:
		ctr = ctr + n // tf
		tf = tf * f
	if i == 0:
		mini = ctr // fc
	else:
		mini = min(mini, ctr // fc)
	i = i + 1
print(mini)


import math

def calc(p, q):
	cnt = 0
	for i in range(1, 1000):
		if p ** i > n:
			break
		else:
			cnt += n // p ** i
			if n // p ** i < p:
				break
	return cnt // q
ans = 10 ** 18
(n, k) = input().split()
n = int(n)
k = int(k)
k1 = k
for i in range(2, int(math.sqrt(k1)) + 1):
	if k % i == 0:
		temp = 0
		while k % i == 0:
			k //= i
			temp += 1
		ans = min(ans, calc(i, temp))
if k > 1:
	ans = min(ans, calc(k, 1))
print(ans)


def factor(n):
	ans = {}
	d = 2
	while d * d <= n:
		if n % d == 0:
			ans[d] = ans.get(d, 0) + 1
			n //= d
		else:
			d += 1
	if n > 1:
		ans[n] = ans.get(n, 0) + 1
	return ans

def find_max_prime_pow_in_fac(n, p):
	ans = 0
	while n > 0:
		ans += n // p
		n //= p
	return ans
(n, k) = map(int, input().split())
factorization = factor(k)
ans = float('inf')
for i in factorization.keys():
	cur_pow = find_max_prime_pow_in_fac(n, i)
	ans = min(ans, cur_pow // factorization[i])
print(ans)


(n, b) = [int(i) for i in input().split()]
from collections import defaultdict
d = defaultdict(lambda : 0)
total = defaultdict(lambda : 0)
ans = float('infinity')
for i in range(2, b):
	if i * i > b:
		break
	if b % i == 0:
		j = i
		while j <= n:
			total[i] += n // j
			j *= i
	while b and b % i == 0:
		b //= i
		d[i] += 1
	if d[i]:
		ans = min(ans, total[i] // d[i])
if b > 1:
	just = 0
	j = b
	while j <= n:
		just += n // j
		j *= b
	ans = min(ans, just)
print(ans)


import os
import sys
from collections import deque
import pdb
import heapq
from heapq import *
from pprint import pprint
from bisect import *
from math import *
if os.getcwd() == 'C:\\Users\\User\\Desktop\\python\\Prog':
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def rI():
	return [int(i) for i in input().split()]
(n, b) = rI()
nado = {}
est = {}
for i in range(2, int(sqrt(b)) + 1):
	if b % i == 0:
		nado[i] = 0
	while b % i == 0:
		nado[i] += 1
		b //= i
if b > 1:
	nado[b] = 1
out = 1e+100
for (key, val) in nado.items():
	est = 0
	curr = n // key
	est += curr
	while curr != 0:
		curr //= key
		est += curr
	out = min(out, est // val)
if out == 1e+100:
	print(0)
else:
	print(out)


mp = dict()

def factorize(n):
	for i in range(2, n):
		if i * i > n:
			break
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				cnt += 1
				n //= i
			mp[i] = cnt
	if n > 1:
		mp[n] = 1

def legendre(n, p):
	ans = 0
	tmp = p
	while n // tmp != 0:
		ans += n // tmp
		tmp *= p
	return ans
(n, b) = map(int, input().split())
factorize(b)
ans = 10 ** 20
for p in mp:
	c = mp[p]
	pow = legendre(n, p)
	pow //= c
	ans = min(ans, pow)
print(ans)


import math

def count_factors(n, p):
	result = 0
	while n >= p:
		n //= p
		result += n
	return result
(n, b) = map(int, input().split())
m = math.inf
for p in range(2, int(math.sqrt(b)) + 1):
	power = 0
	while b % p == 0:
		power += 1
		b //= p
	if power != 0:
		m = min(m, count_factors(n, p) // power)
if b > 1:
	m = min(m, count_factors(n, b))
print(m)


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter, OrderedDict
import threading

def main():
	(n, b) = map(int, input().split())
	i = 2
	prime = []
	while i ** 2 <= b:
		(x, y) = (i, 0)
		while b % i == 0:
			y += 1
			b //= i
		if y:
			prime.append([x, y])
		i += 1
	if b > 1:
		prime.append([b, 1])
	ans = float('inf')
	for D in prime:
		(x, y, z) = (D[0], D[1], 0)
		i = x
		while i <= n:
			z += n // i
			i *= x
		ans = min(ans, z // y)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def prime(n):
	import math
	d = 2
	if n == 2:
		return {2: 1}
	prime_dict = dict()
	while n >= d and math.sqrt(n) >= d:
		if n % d == 0:
			if prime_dict.get(d):
				prime_dict[d] = prime_dict[d] + 1
			else:
				prime_dict[d] = 1
			n = int(n / d)
		else:
			d = d + 1
	if prime_dict.get(n):
		prime_dict[n] = prime_dict[n] + 1
	else:
		prime_dict[n] = 1
	return prime_dict
_ = input()
(n, d) = _.split()
(n, d) = (int(n), int(d))
prime_dict = prime(d)
n_prime_dict = dict()
answer = n
for key in prime_dict:
	_pow_key = key
	n_prime_key = 0
	while _pow_key <= n:
		n_prime_key = n_prime_key + n // _pow_key
		_pow_key = _pow_key * key
	answer = min(answer, n_prime_key // prime_dict[key])
print(answer)


import math
(n, b) = map(int, input().split())
dic = {}
i = 2
startB = b
while b > 1:
	if i > int(math.sqrt(b)):
		dic.update({b: 1})
		break
	while b > 1 and b % i == 0:
		if i in dic.keys():
			dic[i] += 1
		else:
			dic.update({i: 1})
		b = b // i
	i += 1
pic = {}
keys = list(dic.keys())
for x in keys:
	count = 0
	for i in range(1, n):
		t = n // x ** i
		count += t
		if t == 0:
			break
	pic.update({x: count})
mn = 1e+101
for x in keys:
	t = pic[x] // dic[x]
	if t < mn:
		mn = t
print(mn)


def deli(b):
	i = 2
	ans = []
	while i * i <= b:
		if b % i == 0:
			cnt = 0
			while b % i == 0:
				b //= i
				cnt += 1
			ans.append([i, cnt])
		i += 1
	if b != 1:
		ans.append([b, 1])
	return ans
(n, b) = map(int, input().split())
k = deli(b)
ans = 100000000000000000000
for i in k:
	cnt = 0
	a = i[0]
	while a <= n:
		cnt += n // a
		a *= i[0]
	ans = min(ans, cnt // i[1])
print(ans)


(n, b) = [int(x) for x in input().split()]

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors

def count_k_p(n, p):
	i = p
	sum = 0
	while i <= n:
		sum += n // i
		i *= p
	return sum
import math
k = math.inf
prime_factors_list = prime_factors(b)
prime_factors_set = set(prime_factors_list)
for i in prime_factors_set:
	k = min(k, count_k_p(n, i) // prime_factors_list.count(i))
print(k)


def factorize(n):
	factors = []
	for i in range(2, int(n ** 0.5) + 1):
		cnt = 0
		while n % i == 0:
			n //= i
			cnt += 1
		if cnt > 0:
			factors.append((i, cnt))
	if n != 1:
		factors.append((n, 1))
	return factors
(n, b) = map(int, input().split())
factors = factorize(b)
x = float('inf')
for (f, c) in factors:
	div_c = 0
	for e in range(1, 100):
		if f ** e > n:
			break
		div_c += n // f ** e
	x = min(x, div_c // c)
print(x)


import sys
from collections import deque
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
li = lambda : list(input_())
pr = lambda x: print(x)
f = lambda : sys.stdout.flush()
(n, k) = il()
d = {}
x = int(k ** 0.5)
for i in range(2, x + 2):
	while k % i == 0:
		if d.get(i):
			d[i] += 1
		else:
			d[i] = 1
		k = k // i
if k != 1:
	if d.get(k):
		d[k] += 1
	else:
		d[k] = 1
ans = float('inf')
for i in d:
	c = 0
	te = n
	while te > 0:
		te = te // i
		c += te
	ans = min(ans, c // d[i])
print(ans)


import math

def prime_factorization(x):
	answer = {}
	i = 2
	while i * i <= x:
		if x % i == 0:
			cnt = 0
			while x % i == 0:
				x //= i
				cnt += 1
			answer[i] = cnt
		i += 1
	if x > 1:
		answer[x] = 1
	return answer
test = 1
for tes in range(test):
	(n, b) = list(map(int, input().split()))
	facs = prime_factorization(b)
	ans = -1
	d = {}
	for (x, v) in facs.items():
		p = x
		cnt = 0
		while p <= n:
			cnt += n // p
			p = p * x
		d[x] = cnt // v
	for (k, v) in d.items():
		if ans == -1:
			ans = v
		else:
			ans = min(ans, v)
	x = int(math.sqrt(b))
print(ans)


(n, b) = [int(x) for x in input().split()]
i = 2
ans = -1

def update(p):
	cnt = 0
	tmp = p
	while tmp <= n:
		cnt += n // tmp
		tmp *= p
	return cnt
while i * i <= b:
	if b % i == 0:
		q = 0
		while b % i == 0:
			b //= i
			q += 1
		cnt = update(i)
		if ans == -1:
			ans = cnt // q
		else:
			ans = min(ans, cnt // q)
	i += 1
if b > 1:
	cnt = update(b)
	if ans == -1:
		ans = cnt
	else:
		ans = min(ans, cnt)
print(ans)


import math

def count_factors(n, p):
	result = 0
	while n >= p:
		n //= p
		result += n
	return result

def sieve(x):
	a = [True] * x
	a[0] = a[1] = False
	for (i, is_prime) in enumerate(a):
		if is_prime:
			yield i
			for n in range(i * i, x, i):
				a[n] = False
(n, b) = map(int, input().split())
primes = sieve(int(math.sqrt(b)) + 1)
m = math.inf
found = False
for p in primes:
	power = 0
	while b % p == 0:
		power += 1
		b //= p
	if power != 0:
		m = min(m, count_factors(n, p) // power)
		found = True
if b > 1:
	m = min(m, count_factors(n, b))
print(m)


import math

def d(x, y, z):
	s = 0
	se = x
	while z >= se:
		s += int(z // se)
		se *= x
	s = int(s // y)
	return s
(n, b) = map(int, input().split())
i = 2
ans = -1
while i <= math.sqrt(b):
	if b % i == 0:
		j = 0
		while b % i == 0:
			j += 1
			b //= i
		k = d(i, j, n)
		if ans == -1 or k < ans:
			ans = k
	i += 1
if b != 1:
	k = d(b, 1, n)
	if ans == -1 or k < ans:
		ans = k
if ans == -1:
	ans = 0
print(ans)


def getZeros(Mid, B):
	curr = 0
	tmp = B
	while tmp <= Mid:
		curr += Mid // tmp
		tmp *= B
	return curr
sz = 10 ** 6 + 5
primes = []
prime = []

def PreCompute():
	global primes
	global prime
	global sz
	for i in range(sz):
		prime.append(True)
	prime[0] = False
	prime[1] = False
	for i in range(2, sz):
		if prime[i]:
			primes.append(i)
			for j in range(i + i, sz, i):
				prime[j] = False
hehe = dict()
PreCompute()
(N, B) = [int(x) for x in input().split()]
for it in primes:
	if B == 1:
		break
	if B % it != 0:
		continue
	tmp = 0
	while B % it == 0:
		B //= it
		tmp += 1
	hehe[it] = tmp
if B > 1:
	hehe[B] = 1
num = -1
for (key, val) in hehe.items():
	if num == -1:
		num = getZeros(N, key) // val
	else:
		num = min(num, getZeros(N, key) // val)
if num == -1:
	num = 0
print(num)


(n, k) = map(int, input().split())
primecnt = {}

def prime(n):
	if n < 2:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def fun(n, k):
	p = k
	ans = 0
	while p <= n:
		ans += n // p
		p *= k
	return ans
if prime(k):
	print(fun(n, k))
else:
	prime_cnt = {}
	for i in range(2, int(k ** 0.5) + 1):
		if k % i == 0:
			prime_cnt[i] = 0
			while k % i == 0:
				k //= i
				prime_cnt[i] += 1
	if prime(k):
		prime_cnt[k] = 1
	ANS = n
	for i in prime_cnt:
		ANS = min(ANS, fun(n, i) // prime_cnt[i])
	print(ANS)


def get_div(b):
	s = {}
	while b != 1:
		for i in range(2, int(b ** 0.5) + 1):
			if b % i == 0:
				s[i] = s.get(i, 0) + 1
				b //= i
				break
		else:
			s[b] = s.get(b, 0) + 1
			return s
	return s
(n, b) = map(int, input().split())
h = get_div(b)
p = 10 ** 100
for i in h:
	total = 0
	for j in range(1, 1000):
		total += n // i ** j
	total //= h[i]
	p = min(total, p)
print(p)


import math

def prime_factors(n):
	factors = dict()
	while n % 2 == 0:
		if 2 in factors:
			factors[2] += 1
		else:
			factors[2] = 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n / i
	if n > 2:
		factors[n] = 1
	return factors
(n, b) = str(input()).split()
(n, b) = (int(n), int(b))
pfactors = prime_factors(b)
answers = []
for pfactor in pfactors:
	times = pfactors[pfactor]
	divisor = pfactor
	ans = 0
	while n >= divisor:
		ans += n // divisor
		divisor *= pfactor
	answers.append(ans // times)
print(int(min(answers)))


def factors(a):
	f = []
	i = 2
	while i * i <= a:
		if a % i == 0:
			f.append([i, 0])
		while a % i == 0:
			f[len(f) - 1][1] += 1
			a //= i
		i += 1
	if a > 1:
		f.append([a, 1])
	return f
(n, b) = map(int, input().split())
res = factors(b)
kol_f = [0] * len(res)
for i in range(len(res)):
	now = res[i][0]
	while now <= n:
		kol_f[i] += n // now
		now *= res[i][0]
ans = kol_f[0] // res[0][1]
for i in range(1, len(res)):
	ans = min(ans, kol_f[i] // res[i][1])
print(ans)


import math
(n, b) = map(int, input().split())
m = b
dic_prime = dict()
while m % 2 == 0:
	m = m // 2
	c = dic_prime.get(2, 0)
	dic_prime[2] = c + 1
for i in range(3, int(math.sqrt(m) + 1), 2):
	while m % i == 0:
		m = m // i
		c = dic_prime.get(i, 0)
		dic_prime[i] = c + 1
if m > 2:
	dic_prime[m] = 1
count_zeros = n
for p in list(dic_prime.keys()):
	m = n
	count_p = m // p
	x = p * p
	while m > x:
		count_p += m // x
		x = x * p
	co = count_p // dic_prime[p]
	if count_zeros > co:
		count_zeros = co
print(count_zeros)


def prime_decomposition(n):
	i = 2
	table = []
	while i * i <= n:
		while n % i == 0:
			n /= i
			table.append(i)
		i += 1
	if n > 1:
		table.append(int(n))
	return table
from collections import Counter
(n, b) = list(map(int, input().split()))
primes = Counter(prime_decomposition(b))
res = []
for (x, y) in primes.items():
	c = 0
	xx = x
	while 0 < n // xx:
		c += n // xx
		xx = xx * x
	res.append(c // y)
print(min(res))


import math

def primes(n):
	primfac = []
	i = 0
	while n % 2 == 0:
		n //= 2
		i += 1
	if i > 0:
		primfac.append((2, i))
	d = 3
	while d * d <= n:
		i = 0
		while n % d == 0:
			n //= d
			i += 1
		if i > 0:
			primfac.append((d, i))
		d += 2
	if n > 1:
		primfac.append((n, 1))
	return primfac
(n, b) = [int(s) for s in input().split(' ')]
zeros = 1
primfac = primes(b)
smallest_power = float('Inf')
for (f, p) in primfac:
	power = 0
	div = n // f
	while div > 0:
		power += div
		div = div // f
	power = power // p
	smallest_power = min(power, smallest_power)
print(int(smallest_power))


import math

def primeFactors(n):
	p_factors = []
	while n % 2 == 0:
		(p_factors.append(2),)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			(p_factors.append(i),)
			n = n / i
	if n > 2:
		p_factors.append(n)
	return p_factors
(n, b) = list(map(int, input().split()))
factors = []
factors = primeFactors(b)
unique_f = list(set(factors))
ans = 10 ** 20
for x in unique_f:
	curr_n = n
	curr_ans = 0
	cont = factors.count(x)
	while int(curr_n // x) > 0:
		curr_n = int(curr_n // x)
		curr_ans += curr_n
	ans = min(ans, int(curr_ans // cont))
print(ans)


import math
(n, b) = map(int, input().split())
i = int(math.sqrt(b))
num = dict()
for i in range(2, i + 2):
	while b % i == 0:
		num[i] = num.get(i, 0) + 1
		b = b // i
if b != 1:
	num[b] = num.get(b, 0) + 1
res = int(1e+18)
for f in num:
	t = 0
	temp = n
	while temp > 0:
		temp = temp // f
		t = t + temp
	res = min(res, t // num[f])
print(res)


def factorize(n):
	result = []
	N = n
	i = 2
	while i * i <= N:
		if n % i == 0:
			power = 0
			while n % i == 0:
				n = n // i
				power += 1
			result.append((i, power))
		i += 1
	if n != 1:
		result.append((n, 1))
	return result
(n, b) = input().split()
n = int(n)
b = int(b)
p = factorize(b)
ans = None
for (prime, power) in p:
	k = prime
	pp = 0
	while k <= n:
		pp += n // k
		k *= prime
	res = pp // power
	if ans == None or ans > res:
		ans = res
print(ans)


[n, b] = list(map(int, input().split()))

def factorize(x):
	res = dict()
	d = 2
	while d * d <= x:
		while x % d == 0:
			x //= d
			if d in res:
				res[d] += 1
			else:
				res[d] = 1
		d += 1
	if x > 1:
		res[x] = 1
	return res
res = 0
h = factorize(b)
tmp = int(1e+18)
for (key, val) in h.items():
	n2 = n
	y = 0
	while n // key > 0:
		y += n // key
		n //= key
	tmp = min(tmp, y // val)
	n = n2
if tmp < int(1e+18):
	res += tmp
print(res)


from collections import defaultdict as dd
import math

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))
(n, b) = mi()
pfacs = []
k = 2
temp = b
c = 0
while k <= temp:
	if k * k > b:
		pfacs.append([temp, 1])
		c = 0
		break
	if temp % k == 0:
		temp = temp // k
		c += 1
	else:
		if not c == 0:
			pfacs.append([k, c])
		c = 0
		k += 1
if not c == 0:
	pfacs.append([k, c])
	c = 0
	k += 1
totals = []
for (p, c) in pfacs:
	total = 0
	k = 1
	while p ** k <= n:
		total = total + n // p ** k
		k += 1
	factors = total // c
	totals.append(factors)
print(min(totals))


import sys

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = self.next_line()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_line(self, _map=str):
		return list(map(_map, sys.stdin.readline().split()))

	def next_int(self):
		return int(self.next())

	def solve(self):
		(n, b) = self.next_line(int)
		rs = -1
		for i in range(2, 1000001):
			if b % i == 0:
				ct = 0
				while b % i == 0:
					b //= i
					ct += 1
				t = self.cal(n, i)
				tt = t // ct
				if rs == -1 or tt < rs:
					rs = tt
		if b > 1:
			t = self.cal(n, b)
			if rs == -1 or t < rs:
				rs = t
		print(rs)

	def cal(self, n, k):
		return 0 if n == 0 else n // k + self.cal(n // k, k)
Main().solve()


import math

def fact(n, p):
	countt = 0
	i = p
	while True:
		tmp = n // i
		countt += tmp
		i *= p
		if tmp == 0:
			break
	return countt
(n, b) = map(int, input().split())
ans = math.inf
bb = b
i = 2
while i * i <= bb:
	if b % i == 0:
		countt = 0
		while b % i == 0:
			b = b // i
			countt = countt + 1
		tmp = fact(n, i) // countt
		if tmp < ans:
			ans = tmp
	i = i + 1
if b != 1:
	tmp = fact(n, b)
	if tmp < ans:
		ans = tmp
print(ans)


(n, b) = map(int, input().split())
pws = dict()
i = 2
while i * i <= b:
	while b % i == 0:
		b //= i
		pws[i] = pws.get(i, 0) + 1
	i += 1
if b > 1:
	pws[b] = 1
m = None
for (dvs, pwr) in pws.items():
	(d, k) = (1, 0)
	while True:
		d *= dvs
		a = n // d
		if a == 0:
			break
		k += a
	k //= pwr
	if m is None or k < m:
		m = k
print(m)


size = 1000010
is_prime = [True] * size
for i in range(2, size):
	if is_prime[i]:
		for j in range(i * i, size, i):
			is_prime[j] = False
primes = [i for i in range(2, size) if is_prime[i]]
(num, base) = tuple([int(x) for x in input().split(' ')])
temp = base
factors = []
for i in primes:
	if not temp % i:
		cnt = 0
		while temp % i == 0:
			cnt += 1
			temp /= i
		factors.append((i, cnt))
if temp > 1:
	factors.append((temp, 1))
ans = 10000000000000000000000000000000000000
for f in factors:
	(cnt, i) = (0, f[0])
	while i <= num:
		cnt += num // i
		i *= f[0]
	ans = min(ans, cnt // f[1])
print(int(ans))


import math
(n, b) = map(int, input().split())
x = b
nn = n
l = []
ll = []
if b % 2 == 0:
	l.append(2)
	ll.append(0)
while b % 2 == 0:
	b = b // 2
	ll[-1] += 1
for i in range(3, int(math.sqrt(b)) + 1, 2):
	if b % i == 0:
		l.append(i)
		ll.append(0)
	while b % i == 0:
		b = b // i
		ll[-1] += 1
if b > 2:
	l.append(b)
	ll.append(1)
mi = 1e+200
for i in range(len(l)):
	count = 0
	cc = ll[i]
	tt = l[i]
	i = tt
	while nn // i >= 1:
		count += nn // i
		i *= tt
	mi = min(mi, count // cc)
if mi == 1e+200:
	mi = 0
print(mi)


(n, b) = map(int, input().split())
num = -1
i = 2
k = b
factors = []
while k != 1 and i < int(b ** 0.5) + 3:
	if k % i == 0:
		factors.append(i)
		while k % i == 0:
			k = k // i
	i += 1
if k != 1:
	factors.append(k)
if not factors:
	ans = 0
	k = 1
	while b ** k <= n:
		ans += n // b ** k
		k += 1
	print(ans)
	exit()
ans = 10 ** 18
for num in factors:
	count = 0
	k = n
	while b % num == 0:
		b = b // num
		count += 1
	maxx = 0
	k = 1
	while num ** k <= n:
		maxx += n // num ** k
		k += 1
	ans = min(ans, maxx // count)
print(ans)


import math
from collections import Counter
import decimal
ctx = decimal.Context()

def isp(num):
	for i in range(2, int(math.sqrt(num)) + 1):
		if num % i == 0:
			return False
	return True

def float_to_str(f):
	d1 = ctx.create_decimal(repr(f))
	return format(d1, 'f')

def fac(num):
	re = []
	for i in range(2, int(math.sqrt(num)) + 1):
		if isp(i):
			if num % i == 0:
				re.append(i)
				num /= i
				while num % i == 0 and num != 0:
					num /= i
					re.append(i)
	if num != 1:
		re.append(int(num))
	return re

def count(n, f):
	logg = int(math.log(n, f))
	summ = logg * (logg + 1) // 2 - logg
	return n // f + summ

def count2(n, f):
	re = 0
	while n:
		re += n // f
		n //= f
	return re
(n, b) = map(int, input().strip().split())
factor = fac(b)
s_f = set(factor)
co = {}
for i in s_f:
	co[i] = count2(n, i)
cc = Counter(factor)
mm = int(1e+200)
for (a, c) in cc.items():
	if a in co:
		mm = min(mm, co[a] // c)
	else:
		mm = 0
print(float_to_str(mm))


import math
import sys
(n, b) = list((int(i) for i in input().split()))

def primefactorizaton(b):
	i = 2
	p = []
	while b % i == 0:
		p.append(2)
		b //= 2
	for i in range(3, int(math.sqrt(b)) + 1, 2):
		if b % i == 0:
			while b % i == 0:
				p.append(i)
				b //= i
	if b > 2:
		p.append(b)
	return p

def powr(r, s, n):
	w = r
	alpha = 0
	while n // w != 0:
		alpha += n // w
		w *= r
	alpha //= s
	return alpha
X = primefactorizaton(b)
dict = {}
for ele in X:
	if ele not in dict:
		dict[ele] = 1
	else:
		dict[ele] += 1
ans = 10 ** 25
for ele in dict:
	ans = min(ans, powr(ele, dict[ele], n))
print(ans)


from math import sqrt, floor
(n, b) = map(int, input().split())

def find(n, factors):
	cnt = {}
	for k in factors:
		cnt[k] = 0
		i = k
		while n // i >= 1:
			cnt[k] += n // i
			i *= k
	return cnt

def factorize(n):
	factors = {}
	while n % 2 == 0:
		factors[2] = factors.get(2) + 1 if factors.get(2) else 1
		n /= 2
	for i in range(3, floor(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors[i] = factors.get(i) + 1 if factors.get(i) else 1
			n /= i
	if n > 2:
		factors[int(n)] = 1
	return factors
fk = factorize(b)
fn = find(n, fk)
m = 10 ** 19
for i in fk.keys():
	if not fn.get(i):
		print(0)
		exit(0)
	else:
		m = min(m, fn[i] // fk[i])
print(m)


def getP(b):
	d = 2
	a = []
	while d * d <= b:
		if b % d == 0:
			p = d
			deg = 0
			while b % d == 0:
				b //= d
				deg += 1
			a.append((p, deg))
		d += 1
	if b != 1:
		a.append((b, 1))
	return a
(n, b) = map(int, input().split())
a = getP(b)
ans = 10 ** 20
for (p, deg) in a:
	cur = p
	res = 0
	while cur <= n:
		res += n // cur
		cur *= p
	ans = min(ans, res // deg)
print(ans)


def rwh_primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
primes = rwh_primes(1500000)

def fact(m):
	res = []
	for p in primes:
		if m % p == 0:
			k = 0
			while m % p == 0:
				k += 1
				m //= p
			res.append((p, k))
			if m == 1:
				return res
	res.append((m, 1))
	return res
(n, b) = map(int, input().split())
res = -1
for (p, k) in fact(b):
	t = 0
	pp = p
	while pp <= n:
		t += n // pp
		pp *= p
	if res < 0:
		res = t // k
	else:
		res = min(res, t // k)
print(res)


import math
(n, b) = map(int, input().split())
maxdel = int(math.sqrt(b)) + 1
cur = 2
globk = 1000000000000000000000000000000000000000000000
while cur < maxdel:
	ncopy = n
	curprozv = 0
	while b % cur == 0:
		curprozv += 1
		b //= cur
	if curprozv != 0:
		k = 0
		while ncopy > 0:
			k += ncopy // cur
			ncopy //= cur
		globk = min(k // curprozv, globk)
	cur += 1
if b != 1:
	k = 0
	while n > 0:
		k += n // b
		n //= b
	globk = min(k, globk)
print(globk)


from collections import defaultdict as dd
import math
(num, b) = map(int, input().split())
n = b
ans = 1e+18
d = dd(int)
while n % 2 == 0:
	n = n // 2
	d[2] += 1
for i in range(3, int(math.sqrt(n)) + 1, 2):
	while n % i == 0:
		d[i] += 1
		n = n // i
if n > 2:
	d[n] += 1
for i in d:
	x = 0
	z = num
	while z:
		z //= i
		x += z
	ans = min(x // d[i], ans)
else:
	print(ans)


(N, B) = [int(x) for x in input().split()]
v = []
for i in range(2, 10 ** 6 + 1000):
	while B % i == 0:
		v.append(i)
		B //= i
if B != 1:
	v.append(B)

def zeros(p, v, N):
	res = 0
	pk = p
	while pk <= N:
		res += N // pk
		pk *= p
	res //= v.count(p)
	return res
print(min((zeros(x, v, N) for x in v)))


import sys
import heapq
import math

def factorise(n):
	factors = []
	while n % 2 == 0:
		n //= 2
		factors.append(2)
	for i in range(3, n + 1, 2):
		if n == 1:
			return factors
		while n % i == 0:
			n //= i
			factors.append(i)
		if i == 1:
			return factors
		if i ** 2 > n and n != 1:
			factors.append(n)
			return factors
	return factors
lines = sys.stdin.read().splitlines()
(n, b) = [int(x) for x in lines[0].split(' ')]
factors = factorise(b)
factorCounts = {}
for factor in factors:
	if factor in factorCounts:
		factorCounts[factor] += 1
	else:
		factorCounts[factor] = 1
count = 0
numberFactorCounts = {}
for factor in factorCounts:
	baseFactor = factor
	while factor <= n:
		count += n // factor
		factor *= baseFactor
	numberFactorCounts[baseFactor] = count
	count = 0
vals = []
for factor in factorCounts:
	if factor in numberFactorCounts:
		val = numberFactorCounts[factor] // factorCounts[factor]
		vals.append(val)
	else:
		vals.append(0)
print(min(vals))


import math
import collections
import bisect
import heapq
import time
import itertools
import sys

def decomp(val):
	d = 2
	ans = collections.defaultdict(int)
	while d <= math.sqrt(val):
		if val % d == 0:
			while val % d == 0:
				ans[d] += 1
				val //= d
		d += 1
	if val > 1:
		ans[val] += 1
	return ans
(N, B) = map(int, input().split())
comps = decomp(B)
ans = float('inf')
for y in comps.keys():
	z = y
	x = 0
	while z <= N:
		x += N // z
		z *= y
	ans = min(ans, x // comps[y])
print(ans)


input = __import__('sys').stdin.readline
print = __import__('sys').stdout.write
(n, b) = map(int, input().split())
a = [True] * (int(b ** 0.5) + 4)
a[0] = False
a[1] = False
p = []
length = len(a)
for i in range(2, length):
	if a[i]:
		p.append(i)
		for j in range(2 * i, length, i):
			a[j] = False
l = {}
idx = 0
try:
	while b != 1:
		if b % p[idx] == 0:
			b /= p[idx]
			if p[idx] not in l:
				l[p[idx]] = 1
			else:
				l[p[idx]] += 1
		else:
			idx += 1
except IndexError:
	l[b] = 1
final = []
for (k, v) in l.items():
	ans = 0
	current_key = k
	while current_key <= n:
		ans += n // current_key
		current_key *= k
	final.append(int(ans // v))
print(str(min(final)))


def y(b):
	mx = 0
	res = {}
	for i in range(2, int(b ** 0.5) + 1):
		while b % i == 0:
			mx = i
			res[i] = res.get(i, 0) + 1
			b //= i
	if b != 1:
		mx = b
		res[b] = 1
	return res
(n, b) = map(int, input().split())
k = y(b)
a = []
for i in k:
	a.append(0)
	m = i
	while m <= n:
		a[-1] += n // m
		m *= i
	a[-1] //= k[i]
print(min(a))


(n, b) = map(int, input().split())

def pow(n, b):
	ans = 0
	while n:
		n //= b
		ans += n
	return ans
ans = n
for p in range(2, b):
	if p ** 2 > b:
		break
	exp = 0
	while b % p == 0:
		b //= p
		exp += 1
	if exp:
		ans = min(ans, pow(n, p) // exp)
if b != 1:
	ans = min(ans, pow(n, b))
print(ans)


def factorize(n):
	v = []
	ct = 0
	while n % 2 == 0:
		n = n // 2
		ct += 1
	if ct > 0:
		v.append((2, ct))
	ma = int(n ** 0.5)
	for i in range(3, ma + 1, 2):
		ct = 0
		while n % i == 0:
			ct += 1
			n = n // i
		if ct > 0:
			v.append((i, ct))
	if n > 2:
		v.append((n, 1))
	return v
(n, b) = input().split()
n = int(n)
b = int(b)
fact = factorize(b)
l = len(fact)
ans = -1
for i in range(l):
	m = fact[i][0]
	ct = 0
	num = n
	denum = m
	while True:
		tmp = num // denum
		ct += tmp
		denum = denum * m
		if tmp == 0:
			break
	ct = ct // fact[i][1]
	if ans == -1:
		ans = ct
	else:
		ans = min(ans, ct)
print(ans)


import math
(N, B) = map(int, input().split())

def primeFactors(n):
	A = []
	while n % 2 == 0:
		A.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			A.append(i)
			n = n // i
	if n > 2:
		A.append(n)
	return A
E = primeFactors(B)
C = list(set(E))
V = []
for i in C:
	j = 1
	S = 0
	while N // i ** j >= 1:
		S += N // i ** j
		j += 1
	V.append(S // E.count(i))
print(min(V))


(n, b) = map(int, input().split())
import math
x = int(math.sqrt(b))
fa = dict()
for i in range(2, x + 2):
	while b % i == 0:
		fa[i] = fa.get(i, 0) + 1
		b = b // i
if b != 1:
	fa[b] = fa.get(b, 0) + 1
ans = int(1e+18)
for f in fa:
	t = 0
	tem = n
	while tem > 0:
		tem //= f
		t += tem
	ans = min(ans, t // fa[f])
print(ans)


import math
from collections import defaultdict

def get_primes(upper_bound):
	p = set(range(2, upper_bound + 1))
	for i in range(2, upper_bound + 1):
		if i not in p:
			continue
		for j in range(i * 2, upper_bound + 1, i):
			if j in p:
				p.remove(j)
	return p

def prime_factorization(v, prime_set):
	r = defaultdict(int)
	for p in prime_set:
		while v > 0 and v % p == 0:
			r[p] += 1
			v //= p
	if v > 1:
		r[v] = 1
	return r

def get_count(n, p):
	r = 0
	v = p
	while n >= v:
		r += n // v
		v *= p
	return r
(n, b) = map(int, input().split())
primes = get_primes(int(math.sqrt(b)) + 1)
factorized_n = prime_factorization(b, primes)
v = float('inf')
for (prime_num, prime_count) in factorized_n.items():
	n_has_count = get_count(n, prime_num)
	v = min(v, n_has_count // prime_count)
print(v)


from sys import stdin, stdout
from collections import Counter
(n, b) = [int(x) for x in stdin.readline().rstrip().split()]

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
counter = Counter(prime_factors(b))
totals = {}
for p in counter.keys():
	total = 0
	n_aux = n
	while n_aux > 1:
		n_aux //= p
		total += n_aux
	totals[p] = total
ans = min((totals[p] // f for (p, f) in counter.items()))
print(ans)


data = []

def get_factors(n):
	for i in range(2, int(n ** 0.5) + 2):
		if n % i == 0:
			ans = 0
			while n % i == 0:
				n = n // i
				ans += 1
			data.append([i, ans])
	if n != 1:
		data.append([n, 1])
(n, b) = map(int, input().split())
get_factors(b)
ans = -1
for i in data:
	req = i[1]
	st = i[0]
	cnt = 0
	while True:
		if n < st:
			break
		cnt += n // st
		st = st * i[0]
	val = cnt // req
	if ans == -1:
		ans = val
	else:
		ans = min(ans, val)
if ans == -1:
	ans = 0
print(ans)


(a, b) = map(int, input().split())
i = 2
ans = 1000000000000000000000000000000000000000000000000000000000000000000

def f(p):
	res = 0
	step = p
	while step <= a:
		res += a // step
		step *= p
	return res
while i * i <= b:
	cnt = 0
	while b % i == 0:
		b //= i
		cnt += 1
	if cnt > 0:
		ans = min(ans, f(i) // cnt)
	i += 1
if b > 1:
	ans = min(ans, f(b))
print(ans)


(n, b) = map(int, input().split())
nn = n
j = b
mm = 1
cc = 1
ans = 1000000000000000000000000000000000000000
arr = []
for i in range(2, int(b ** 0.5) + 1):
	if j % i == 0:
		c = 0
		while j % i == 0:
			j = j // i
			c += 1
		arr.append([i, c])
if j > 1:
	mm = j
	ass = 0
	while n:
		ass += n // mm
		n = n // mm
	ans = min(ans, ass)
for i in range(len(arr)):
	xx = nn
	ll = 0
	while xx:
		ll += xx // arr[i][0]
		xx = xx // arr[i][0]
	ans = min(ans, ll // arr[i][1])
print(ans)


(n, b) = map(int, input().split())
ar = []
i = 2
num2 = int(b ** 0.5) + 6
while i < num2:
	num = 0
	while b % i == 0:
		b //= i
		num += 1
	if num > 0:
		ar += [[i, num, 0]]
		if b == 1:
			break
	i += 1
if b != 1:
	ar += [[b, 1, 0]]
ans = 10 ** 30
for i in range(len(ar)):
	num = ar[i][0]
	while n >= num:
		ar[i][2] += n // num
		num *= ar[i][0]
	ans = min(ans, ar[i][2] // ar[i][1])
print(ans)


def compute():
	from sys import stdin
	(n, b) = map(int, stdin.readline().split())

	def genprime(lim):
		a = [True] * lim
		a[0] = a[1] = False
		for (i, x) in enumerate(a):
			if x:
				for y in range(i * i, lim, i):
					a[y] = False
		return list(map(lambda p: p[0], filter(lambda p: p[1], enumerate(a))))
	prime = genprime(int(min(b, 1000000.0)) + 1)

	def isprime(x):
		return x > 1 and (not any((x % f == 0 for f in prime)))

	def cntexp(x):
		ret = {}
		for f in filter(lambda _: x % _ == 0, prime):
			c = 0
			while x % f == 0:
				c += 1
				x //= f
			ret[f] = c
		if isprime(x):
			ret[x] = 1
		return ret

	def cntfct(x, f):
		(ret, fct) = (0, f)
		while x >= fct:
			ret += x // fct
			fct *= f
		return ret
	bcnt = cntexp(b)
	ncnt = {f: cntfct(n, f) for f in bcnt.keys()}
	ret = max(ncnt.values())
	for (k, v) in bcnt.items():
		ret = min(ret, ncnt[k] // v)
	return int(ret)
print(compute())


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inara():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def zero(n, b):
	ans = 0
	now = b
	while now <= n:
		ans += n // now
		now *= b
	return ans
(n, b) = invr()
i = 2
ans = -1
while i * i <= b:
	cnt = 0
	while b % i == 0:
		b //= i
		cnt += 1
	if cnt:
		temp = zero(n, i)
		temp //= cnt
		if ans == -1:
			ans = temp
		else:
			ans = min(ans, temp)
	i += 1
if b > 1:
	temp = zero(n, b)
	if ans == -1:
		ans = temp
	else:
		ans = min(ans, temp)
ans = max(ans, 0)
print(ans)


(n, b) = [int(x) for x in input().strip().split(' ')]
N = int(min(1000000.0, n) + 5)
vis = [0 for _ in range(N)]
primes = []
for i in range(2, N):
	if vis[i] > 0:
		continue
	primes.append(i)
	for j in range(i * i, N, i):
		vis[j] = 1
s = {}
bb = b
for i in primes:
	if i > bb:
		break
	if bb % i == 0:
		c = 0
		while bb % i == 0:
			bb //= i
			c += 1
		s[i] = c
if bb != 1:
	s[bb] = 1
f = {}
for p in s:
	c = 0
	pp = p
	while pp <= n:
		c += n // pp
		pp *= p
	f[p] = c // s[p]
print(min(list(f.values())))
pass


from math import sqrt

def fact(n):
	global g
	global h
	for i in range(2, int(sqrt(n)) + 1):
		k = 0
		if n % i == 0:
			g.append(i)
		while n % i == 0:
			n = n // i
			k += 1
		if k != 0:
			h.append(k)
	if n > 1:
		g.append(n)
		h.append(1)
(n, k) = map(int, input().split())
g = []
h = []
f = fact(k)
min1 = 10 ** 18 + 10
for i in range(len(g)):
	q = 0
	v = g[i]
	while n // g[i] > 0:
		q += n // g[i]
		g[i] *= v
	if q // h[i] < min1:
		min1 = q // h[i]
print(min1)


(n, b) = [int(x) for x in input().split()]

def mno(n):
	Ans = []
	d = 2
	while d * d <= n:
		if n % d == 0:
			Ans.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		Ans.append(n)
	return Ans
tot = mno(b)
counter = {}
maximka = 10 ** 200
for item in tot:
	i = 1
	counter[item] = 0
	while item ** i <= n:
		if item in counter:
			counter[item] += n // item ** i
		else:
			counter[item] = n // item ** i
		i += 1
dic = {}
for item in tot:
	if item in dic:
		dic[item] += 1
	else:
		dic[item] = 1
for item in tot:
	if counter[item] // dic[item] < maximka:
		maximka = counter[item] // dic[item]
print(maximka)


def pf(a):
	factors = []
	if a % 2 == 0:
		ch = 0
		while a % 2 == 0:
			a //= 2
			ch += 1
		factors.append([2, ch])
	i = 3
	while i * i <= a:
		if a % i == 0:
			ch = 0
			while a % i == 0:
				a //= i
				ch += 1
			factors.append([i, ch])
		i += 2
	if a > 1:
		factors.append([a, 1])
	return factors

def smm(a, i):
	ans = 0
	while a:
		ans += a // i
		a //= i
	return ans
(n, b) = map(int, input().split())
ans = n
f = pf(b)
for (i, j) in f:
	ans = min(ans, smm(n, i) // j)
print(ans)


from sys import stdin
import math
(n, m) = map(int, stdin.readline().strip().split())

def trans(n, b):
	s = []
	while n >= b:
		x = n // b
		s.append(n - x * b)
		n = x
	s.append(n)
	s.reverse()
	return s
d = dict()

def pri(n):
	while n % 2 == 0:
		if 2 not in d:
			d[2] = 1
		else:
			d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
			n = n / i
	if n > 2:
		if n not in d:
			d[n] = 1
		else:
			d[n] += 1
d1 = dict()
pri(m)
ans = -1
for i in d:
	d1[i] = 0
	x = i
	y = 0
	z = i
	while x <= n:
		y += n // x
		x *= z
	d1[i] = y
	if ans == -1 or d1[i] // d[i] < ans:
		ans = d1[i] // d[i]
print(int(ans))


from collections import defaultdict

def getPrimeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	k = 3
	while k * k <= n:
		if n % k == 0:
			n = n // k
			factors.append(k)
		else:
			k += 2
	if n > 1:
		factors.append(n)
	return factors
(n, b) = map(int, input().split())
factors_b = getPrimeFactors(b)
count = defaultdict(int)
for a in factors_b:
	count[a] += 1
r = float('inf')
for (y, cnt) in count.items():
	xi = 0
	a = n
	while a != 0:
		xi += a // y
		a //= y
	r = min(r, xi // cnt)
print(r)


import sys
import math
from collections import defaultdict, deque
import heapq
(n, b) = map(int, sys.stdin.readline().split())
primes = defaultdict(int)
newb = b
for i in range(2, int(math.sqrt(b)) + 1):
	if b % i == 0:
		while b % i == 0:
			primes[i] += 1
			b //= i
if b != 1:
	primes[b] += 1
mp = defaultdict(int)
ans = 1e+40
for i in primes:
	num = n
	pr = i
	rem = i
	while pr <= num:
		mp[rem] += num // pr
		pr *= rem
	y = mp[rem] // primes[i]
	ans = min(ans, y)
print(ans)


import math
(N, n) = map(int, input().split())
v = []
b = n
if 1 == 1:
	id = 0
	if n % 2 == 0:
		v.append([2, 0])
		while n % 2 == 0:
			v[id][1] += 1
			n = n // 2
		id += 1
	length = int(math.sqrt(n)) + 1
	for i in range(3, length, 2):
		if n % i == 0:
			v.append([i, 0])
			while n % i == 0:
				v[id][1] += 1
				n = n // i
			id += 1
	if n > 2:
		v.append([n, 1])
l = len(v)
res = 10000000000000000000000000
for i in range(l):
	x = v[i][0]
	temp = 0
	while N // x != 0:
		temp += N // x
		x *= v[i][0]
	temp //= v[i][1]
	res = min(res, temp)
print(res)


import math

def solve(n):
	arr = []
	cnt = 0
	if n % 2 == 0:
		while n % 2 == 0:
			n = n // 2
			cnt += 1
		arr.append((2, cnt))
	for i in range(3, math.floor(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				n = n // i
				cnt += 1
			arr.append((i, cnt))
	if n > 2:
		arr.append((n, 1))
	return arr
(n, b) = map(int, input().split())
a = solve(b)
ans = 1000000000000000000000
for i in range(len(a)):
	x = a[i][0]
	y = a[i][1]
	v = a[i][0]
	u = 0
	while v <= n:
		u += n // v
		v *= x
	ans = min(ans, u // y)
print(ans)


import sys
(n, k) = map(int, input().split())
if n == 1:
	print('0')
	sys.exit(0)
m = k
f = []
i = 2
while i * i <= m:
	if m % i == 0:
		p = 0
		while m % i == 0:
			m //= i
			p += 1
		f.append((i, p))
	i += 1
if m != 1:
	f.append((m, 1))
ans = 10 ** 20
for (x, p) in f:
	q = 0
	y = x
	while y <= n:
		q += n // y
		y *= x
	s = q // p
	ans = min(ans, s)
print(ans)


import math
from collections import defaultdict
mp = defaultdict(int)

def primeFactor(a):
	i = 2
	while i * i <= a:
		while a % i == 0:
			mp[i] += 1
			a //= i
		i += 1
	if a > 1:
		mp[a] += 1

def trailingZero(a, n):
	ans = 0
	while n > 0:
		ans += n // a
		n //= a
	return ans
(n, b) = map(int, input().split())
ans = int(1e+50)
primeFactor(b)
for it in mp:
	first = it
	second = mp[it]
	temp = trailingZero(first, n)
	ans = min(ans, temp // second)
print(ans)


import sys
import math
input = sys.stdin.readline

def primefactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
	return l
(n, b) = map(int, input().split())
d = {}
r = {}
p = primefactors(b)
for i in p:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
l = set(p)
for i in l:
	total = 0
	power = 1
	while n // i ** power != 0:
		total += n // i ** power
		power += 1
	u = d[i]
	r[i] = total // u
ans = 10 ** 18
for i in r:
	ans = min(r[i], ans)
print(ans)


def howmany(n, p):
	count = 0
	while n > 0:
		count += n // p
		n = n // p
	return count
l = input().split()
n = int(l[0])
b = int(l[1])
lo = []
i = 2
while i * i <= b:
	if b % i == 0:
		count = 0
		while b % i == 0:
			count += 1
			b = b // i
		lo.append((i, count))
	i += 1
if b != 1:
	lo.append((b, 1))
lfi = []
for i in lo:
	lfi.append(howmany(n, i[0]) // i[1])
print(min(lfi))


from collections import Counter
import math

def primeFactors_b(n):
	factors = []
	degrees = Counter()
	if n % 2 == 0:
		factors.append(2)
		while n % 2 == 0:
			n = n / 2
			degrees[2] += 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			factors.append(i)
			while n % i == 0:
				degrees[i] += 1
				n = n / i
	if n > 2:
		factors.append(n)
		degrees[n] += 1
	return (factors, degrees)

def prime_factors_factorial(n, factors):
	degrees = Counter()
	for i in factors:
		degree = 1
		step = n // i ** degree
		while step > 0:
			degrees[i] += step
			degree += 1
			step = n // i ** degree
	return degrees
(n, b) = map(int, input().split())
(factors_b, degrees_b) = primeFactors_b(b)
degrees_n = prime_factors_factorial(n, factors_b)
min_degree = math.inf
print(int(min((degrees_n[i] // degrees_b[i] for i in factors_b))))


from operator import itemgetter
from math import sqrt
(n, b) = map(int, input().split())

def primefactors(n):
	sq = int(sqrt(n))
	i = 0
	while n % 2 == 0:
		n = n // 2
		i += 1
	if i > 0:
		yield (2, i)
	for j in range(3, sq + 1, 2):
		i = 0
		while n % j == 0:
			n = n // j
			i += 1
		if i > 0:
			yield (j, i)
	if n != 1:
		yield (n, 1)

def f(n, p, k):
	tmp = 0
	x = p
	while x <= n:
		tmp += n // x
		x = x * p
	return tmp // k
a = []
for (p, k) in primefactors(b):
	a.append(f(n, p, k))
print(min(a))


import math
(n, b) = map(int, input().split())
a = []
c = dict()
if b % 2 == 0:
	a.append(2)
	while b % 2 == 0:
		if 2 not in c:
			c[2] = 1
		else:
			c[2] = c[2] + 1
		b //= 2
for i in range(3, math.floor(math.sqrt(b) + 1), 2):
	if b % i == 0:
		a.append(i)
		while b % i == 0:
			if i not in c:
				c[i] = 1
			else:
				c[i] += 1
			b //= i
if b > 2:
	a.append(b)
	c[b] = 1
ans = 1000000000000000000
for i in range(len(a)):
	x = a[i]
	ans1 = 0
	j = x
	while n / j >= 1:
		ans1 += n // j
		j = j * x
	ans1 = ans1 // c[x]
	ans = min(ans, ans1)
print(ans)


(n, b) = list(map(int, input().split()))
now = 1
p = []
isp = [1] * 1000001
for i in range(2, 10 ** 6 + 1):
	if isp[i]:
		p.append(i)
	for x in p:
		if x * i > 1000000:
			break
		isp[x * i] = 0
		if i < x or i % x == 0:
			break
de = []
for prime in p:
	count = 0
	while b % prime == 0:
		b //= prime
		count += 1
	if count:
		de.append((prime, count))
	if b < prime:
		break
if b != 1:
	de.append((b, 1))
ans = 10 ** 20
for pair in de:
	tmp = 1
	has = 0
	(num, count) = (pair[0], pair[1])
	while tmp <= n:
		tmp *= num
		has += n // tmp
	ans = min(ans, has // count)
print(ans)