#include <stdio.h>

int N, B;
int put[16], fac[16];

long long get( int N, int p )
{
	long long NR = 0;
	int cur = 0;
	for (int i = 1; i <= N; i++)
	{
		int j = i;
		for (; j % p == 0; j /= p)
			cur++;
		NR += (long long)cur;
	}
	return NR;
}

int main()
{
	freopen("zero2.in", "rt", stdin);
	freopen("zero2.out", "wt", stdout);

	int T;
	for (T = 1; T <= 10; T++)
	{
		scanf("%d %d", &N, &B);
		fac[0] = 0;
		if ((B & 1) == 0)
		{
			fac[++fac[0]] = 2;
			put[ fac[0] ] = 0;
			for (; (B & 1) == 0; B >>= 1)
				put[ fac[0] ]++;
		}

		for (int i = 3; i * i <= B; i += 2)
			if (B % i == 0)
			{
				fac[++fac[0]] = i;
				put[ fac[0] ] = 0;
				for (; B % i == 0; B /= i)
					put[ fac[0] ]++;
			}

		if (B > 1)
			fac[++fac[0]] = B,
			put[ fac[0] ] = 1;

		long long MIN = (1LL << 60);
		for (int i = 1; i <= fac[0]; i++)
		{
			long long val = get(N, fac[i]) / put[i];
			if (val < MIN)
				MIN = val;
		}
		printf("%lld\n", MIN);
	}
	return 0;
}