#include<stdio.h>
#define N 25
long long v[N],n,p,nr=0;
void desc(){
	long long i;
	for(i=2;i*i<=n;++i)
		if(n%i==0){
			v[++nr]=i;
			while(n%i==0)
				n/=i;
		}
		if(n!=1)
			v[++nr]=n;
}

long long nrp(long long x){
	long long s=0,i,j;
	for(i=0;i<(1<<nr);++i){
		long long copie=i,nrb=0,prod=1;
		for(j=1;j<=nr;++j,copie>>=1)
			if(copie&1){
				prod*=v[j];
				++nrb;
			}
		if(nrb&1)
			s-=x/prod;
		else
			s+=x/prod;
	}
	return s;
}

void bin(long long st,long long dr){
	while(st!=dr){
		long long m=(st+dr)/2;
		if(p<=nrp(m))
			dr=m;
		else
			st=m+1;
	}
	printf("%lld\n",st);
}

int main(){
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	desc();
	bin(1,(long long)1<<(long long)61);
	fclose(stdin);
	fclose(stdout);
	return 0;
}