# include <fstream>
# include <cstdio>
# define  LL  long long
using namespace std;
    LL P, Q, desc[100], cnt, du, d, ap[100], i, de[100], ap2[100], cnt2, afis, var, valoare;
    
	LL des (LL P, LL desc[], LL ap[]){
		du=P;
		cnt=0;
		if (du%2==0){
			desc[++cnt]=2;
			while (du%2==0){
				++ap[cnt];
				du>>=1;
			}
		}
		d=3;
		while (du>1){
			if (du%d==0){
			    desc[++cnt]=d;
		    	while (du%d==0){
			    	++ap[cnt];
			    	du=du/d;
			    }
			}
			d=d+2;
		}
	}
	
	LL corect (LL nr, LL put){
		//vezi de cate ori apare fiecare component in desc lui nr prin impartire
		//ok, let's start ... 
		LL ret=0;
		while (nr){
			nr/=put;
			ret+=nr;
		}
		return ret;
	}
	
	LL cb (LL in, LL sf, LL i){
		LL ret;
		while (in<=sf){
			int m= (in+sf) >> 1;
			if (corect (m, desc[i])>=ap[i]){//search down
				ret=m;
				sf=m-1;
			}
			else in=m+1;//else up
			
		}
		return ret;
	}
	
	int main (){
		ifstream f ("gfact.in");
		freopen ("gfact.out", "w", stdout);
		f>>P>>Q;
		des (P, desc, ap);
		valoare=1;
		valoare=(LL)valoare << 30;
		for (i=1;i<=cnt;++i){
			ap[i]=ap[i]*Q;
			var=cb (1, valoare, i);
			if (afis<var) afis=var;
		}
		printf ("%lld\n", afis);
		return 0;
	}