#include<stdio.h>
#include<string.h>

long long sel[16],v[16],n,k,nr;

long long ver(long long a)
{
	long long s=0,i;
	memset(sel,0,sizeof(sel));
	while(sel[0]==0)
		{
		for(i=nr;i>=0;i--)
			if(sel[i]==0) {sel[i]=1;break;}
			else sel[i]=0;
		long long p=1,t=0;
		for(i=nr;i>=1;i--)
			if(sel[i]) {p*=v[i];t=!t;}
		if(p==1) break;
		if(t==0) s-=a/p;			
		else s+=a/p;
		}
	return a-s;
}

long long cauta(long long a,long long b)
{
	long long c;
	if(a==b) return a;
	c = (a+b)/2;
	if(ver(c)>=k) return cauta(a,c);
	else return cauta(c+1,b);
}

void descompune()
{
	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!=0) v[++nr]=n;
}

int main()
{
	freopen("frac.in","rt",stdin);
	freopen("frac.out","wt",stdout);
	scanf("%lld%lld",&n,&k);
	descompune();
	long long max = 1024*1024*1024;
	max = max *max *2;
	//max = 30;
	printf("%lld\n",cauta(0,max));
	
}