#include <stdio.h>
#include <string.h>

const int N_MAX = 10000;
const long long INF = 200000000000000LL;

long long fact[N_MAX], rez[N_MAX], put[N_MAX];
long long MIN;

long long ap(long long n, long long fac)
{
	long long p = fac, rez = 0;
	while (n / p >= 1) {
		rez += n / p;
		p *= fac;
	}

	return rez;
}


int main()
{
	freopen("zero2.in", "r", stdin);
	freopen("zero2.out", "w", stdout);

	int N, B, T, b, i, j = 0;
	
	for (T = 1; T <= 10; T ++) {		
		scanf("%d %d\n", &N, &B);

		memset(put, 0, sizeof(put));		
		memset(fact, 0, sizeof(fact));
		memset(rez, 0, sizeof(rez));

		b = B;
		for (i = 2; i <= B; i ++) {
			if (b % i == 0) {
				fact[++ fact[0]] = i;
				put[fact[0]] = 1;
				b /= i;
				while (b % i == 0) {
					put[fact[0]] ++;
					b /= i;
				}
			}
		}

		for (i = 1; i <= N; i ++) {
			for (j = 1; j <= fact[0]; j ++) {
				rez[j] += ap(i, fact[j]);
			}
		}

		for (i = 1; i <= fact[0]; i ++) {
			rez[i] = rez[i] / put[i];
		}
		
		MIN = INF;

		for (i = 1; i <= fact[0]; i ++) {
			if (rez[i] < MIN) {
				MIN = rez[i];
			}
		}

		printf("%lld\n", MIN);
	}
	
	return 0;
}