#include <cstdio>

using namespace std;

long long int cautbin(long long f, long long p);
long long int div(long long int n, long long int d);
long long int p, q, rez=-90000;
long long int P;

int main()
{
	freopen("gfact.in", "r", stdin);
	freopen("gfact.out", "w", stdout);
	scanf("%lld %lld", &p, &q);
	long long int f = 2, r, pow = 0;
	P = p;
	while (p > 1)
	{
		pow = 1;
		if (f*f > p)
			f = p;
		while (p%f == 0)
		{
			pow++;
			p = p / f;
		}
		r = cautbin(f, pow*q);
		if (r > rez)
			rez = r;
		f++;
	}
	printf("%lld", rez);
	return 0;
}

long long int cautbin(long long f, long long b)
{
	long long int i = 0;
	long long int pas = 1<<30;
	while (pas != 0)
	{
		if (div(i + pas, f) < q)
			i += pas;
		pas /= 2;
	}
	return i + 1;
}

long long int div(long long int n,long long int d)
{
	long long int r = 0;
	while (n >= d)
	{
		r += n / d;
		n /= d;
	}
	return r;
}