#include <cstdio>
#include <cstdlib>

FILE *fin=fopen("frac.in","r");
FILE *fout=fopen("frac.out","w");

long long b;
long long fact[50];
int nfact;

long long solve(long long a)
{
	long long sum=a;
	for (int i=1; i<(1<<nfact); i++)
	{
		long long nr=1;
		bool par=true;
		for (int j=0; j<nfact; j++)
			if (i&(1<<j))
			{
				par=!par;
				nr*=fact[j];
			}
		sum+=(a/nr)*(par?(1):(-1));
	}
	return sum;	
}

bool lastisok(long long m)
{
	for (int i=0; i<nfact; i++)
		if (!(m%fact[i]))
			return false;
	return true;
}

long long cautbin(long a,long b, long long p)
{
	long long m;
	while (a<b)
	{
		m=(a+b)/2;
		long long res = solve(m);
		if (res<p)
			a=m+1;
		if (res>p)
			b=m-1;
		if (res==p)
		{
			while (!lastisok(m))
				m--;
			return m;
		}
	}
	return a;
}

int main (int argc, char * const argv[]) {
	long long p;
	fscanf(fin, "%lld%lld",&b,&p);
	
	long long pp=2;
	long long x=b;
	while (pp*pp<=b)
	{
		if (!(x%pp))
		{
			x/=pp;
			while (!(x%pp))
				x/=pp;
			fact[nfact++]=pp;
		}
		pp++;
	}
	if (x!=1)
		fact[nfact++]=x;
	
	fprintf(fout,"%lld\n",cautbin(1,(1LL<<61)-1,p));
	fclose(fin);
	fclose(fout);
    return 0;
}