#include<fstream>

using namespace std;


ifstream f("frac.in");
ofstream g("frac.out");
long long v[2000],x[2000],X,n,i,SOL,p,res,k;
void afis(long long A){
	
	long long  sol=1;
	long long nr=0;
	for(long long  i=1;i<=k;i++)
		if(x[i]==1){
			++nr;
			sol*=v[i];
		}
	
	if(nr){
		if(nr%2)
			SOL+=A/sol;
		else
			SOL-=A/sol;
		
	}
	
}
void back(long long niv,long long A){
	
	if(niv==k+1){
		afis(A);
		return ;
	}
	for(int i=0;i<=1;++i){
		x[niv]=i;
		back(niv+1,A);
	}
}
long long  check(long long  A){
	SOL=0;
	back(1,A);
	return (long long )(A-SOL);
}
int cb (long long st,long long dr){
	long long r,mid,pos;
	pos=dr+1;
	while(st<=dr){	
		mid=st+(dr-st)/2;
		 r=check(mid);
		
		if(r>=p){
			dr=mid-1;
			pos=mid;
		}
		else
			st=mid+1;
	}
	return pos;
}
int main () {
	
	f>>n>>p;
	
	
	X=n;
	
	for(i=2; 1LL*i*i<=X ; ++i) {
		if(X%i==0){
			X/=i;
			while(X%i==0)
				X/=i;
			v[++k]=i;
		}
		
	}
	if(X!=1)
		v[++k]=X;
	long long h;
	h=1LL<<61;
	res=cb(1,h);
	g<<res<<"\n";
	return 0;
}