#include<iostream>
#include<fstream>

using namespace std;

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

long long factori[2100], puteri[2100];

inline long long max(long long a, long long b)
{
	return (a > b ? a : b);
}

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

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

long long binar(int fact, int exp)
{
	long long rez, now, med, st = 1, dr = (1 << 60);
	
	while(st <= dr){
		med = (st + dr) >> 1;
		now = putere(fact, med);
		
		if(now >= exp){
			dr = med - 1;
			rez = med;
		}
		else
			st = med + 1;
	}
	
	return rez;
}

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 = max(sol, binar(factori[i], puteri[i]));
	
	out << sol;
	
	return 0;
}