#include<stdio.h>
long long div[15],sol;
long long x;
void apel(long long n,long long i){
	long long nr=0,p=1,pas=0;
	while(i){
		if(i&1){
			p*=div[pas];
			++nr;
		}
		i>>=1;
		++pas;
	}
	if(nr&1)
		sol-=n/p;
	else
		sol+=n/p;
}
long long f(long long n){
	long long i;
	sol=n;
	for(i=1;i<(1<<x);++i)
		apel(n,i);
	return sol;
}
void solve(long long p){
	long long inf=1,sup=2,mij;
	for(mij=1;mij<61;++mij)
		sup*=2;
	sup+=10000;
	sup=(long long)1<<(long long)61;
	while(inf<sup){
		mij=(inf+sup)>>1;
		if(f(mij)>=p)
			sup=mij;
		else
			inf=mij+1;
	}
	
	printf("%lld\n",sup);
}
void diviz(long long n){
	long long i;
	if(n&1)
		x=-1;
	else{
		div[0]=2;
		while(n%2==0)
			n>>=1;
	}
	for(i=3;i*i<=n;++i){
		if(n%i==0){
			div[++x]=i;
			for(;!(n%i);n/=i)
				;
		}
	}
	if(n>1)
		div[++x]=n;
	++x;
}
int main(){
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	long long n,p;
	scanf("%lld%lld",&n,&p);
	diviz(n);
	solve(p);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}