#include<iostream>
#include<fstream>

using namespace std;

ifstream in("gfact.in");
ofstream out("gfact.out");

long long fact[2020], puteri[2020];

inline long long maxim(long long a, long long b)
{
	if(a > b)
		return a;
	return b;
}

void desc(long long n)
{
	long long d = 2, e;
	
	while((d * d <= n) && (n > 1)){
		e = 0;
		
		while((n % d) == 0){
			e++;
			n /= d;
		}
		
		if(e){
			fact[ ++fact[0] ] = d;
			puteri[ ++puteri[0] ] = e;
		}
		
		d++;
	}
	
	if(n > 1){
		fact[ ++fact[0] ] = n;
		puteri[ ++puteri[0] ] = 1;
	}
}

long long putere(long long p, long long n)
{
	long long num = p, s = 0;
	
	while(n){
		n /= num;
		s += n;
	}
	
	return s;
}

long long cautare(long long fact, long long exp)
{
	long long poz = 0, now, med, st = 1, dr = ((fact * exp) << 2);
	
	while(st <= dr){
		//med = (st + dr) >> 1;
		med = (long long)(st + ((dr - st) >> 1));
		now = putere(fact, med);
		
		if(now >= exp){
			dr = med - 1;
			poz = med;
		}
		else
			st = med + 1;
	}
	
	return poz;
}

int main()
{
	long long p, q, sol = (-1), i;
	
	in >> p >> q;
	
	desc(p);
	
	for(i = 1; i <= puteri[0]; ++i)
		puteri[i] *= q;
	
	for(i = 1; i <= puteri[0]; ++i)
		sol = maxim(sol, cautare(fact[i], puteri[i]));
	
	out << sol;
	
	return 0;
}