#include<stdio.h>
long long n, p, prime[15], x;
int nrprime=0, biti;
long long nrp(long long);
void factprim(long long n){
	int i;
	for(i=2; i*i<=n;++i)
		if(n%i==0){
			prime[++nrprime]=i;
			while(n%i==0)
				n/=i;
		}
	if(n!=1)
		prime[++nrprime]=n;
}
void caut(){
	long long st=1, dr=(long long)1<<(long long)61, m;
	while(st!=dr){
		m=(st+dr)/2;
		if(p<=nrp(m))
			dr=m;
		else
			st=m+1;
	}
	printf("%lld", dr);
}
void cautbiti(long long i,long long &prod,int &cate){
	prod=1;
	biti=0;
	cate=0;
	while(i){
		biti++;
		if(i%2==1){
			cate++;
			prod*=prime[biti];
		}
		i/=2;
	}
}
long long nrp(long long x){
	long long s=0,prod;
	int cate;
	for(int i=1;i<(1<<nrprime);++i){
		cautbiti(i,prod,cate);
		if(cate%2==1)
			s+=x/prod;
		else s-=x/prod;
	}
	return x-s;
}

int main(){
	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w",stdout);
	scanf("%lld", &n);
	scanf("%lld", &p);
	factprim(n);
	caut();
	return 0;
}