#include <cstdio>

const long long NMax = (long long)1 << 60;
long long A, Q;

bool rau (long long p1, long long p2) {
	return p2 * Q > p1;
}

long long put (long long n, long long p) {
	long long rez = 0;
	while (n) {
		rez += n / p;
		n /= p;
	}
	return rez;
}

bool desc (long long x,long long a) {
	int p1, p2;
	for (long long i = 2;  i * i <= a; ++i) {
		if (!(a % i)) {
			p1 = put (x, i);
			p2 = 0;
			while (!(a % i)) {
				++p2;
				a /= i;
			}
			if(rau(p1,p2))
				return false;
		}
	}
	if (a != 1) {
		p1 = put (x,a);
		p2 = 1;
		if(rau(p1,p2))
			return false;
	}

	return true;
}

long long BS () {
	long long i, pas = (long long)1 << 60;
	for (i = 0; pas; pas >>= 1) {
		if (!desc(i + pas,A)) {
			i += pas;
		}
	}
	return i + 1;
}

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

	scanf ("%lld%lld", &A, &Q);

	printf ("%lld", BS ());

	return 0;
}