#include <stdio.h>
#define N 1<<7
#define P 1<<18
#define NMAX 1<<61
long long n,p,r,s;
long long v[N],nr[P];
void descompunere()
{
	long long i;
	nr[++s]=1;
	nr[++s]=n;
	for (i=2; i*i<=n; i++)
		if (n%i==0)
		{
			nr[++s]=i;
			nr[++s]=n/i;
			if (nr[s]==nr[s-1])
				s--;
		}
	for (i=2; i*i<=n; i++)
		if (n%i==0)
		{
			v[++r]=i;
			while (n%i==0)
				n/=i;
		}
	if (n!=1)
		v[++r]=n;
}
inline int ok(long long x)//principiul includerii si excluderii
{
	long long rez=x,i,j,part=0,exp;
	for (i=1; i<=s; i++)
	{
		exp=0;
		for (j=1; j<=r; j++)
			if (nr[i]%v[j]==0)
				exp++;
		if (exp&1)
			part-=x/nr[i];
		else
			part+=x/nr[i];
	}
	rez-=part;
	if (rez>=p)
		return 1;
	return 0;
}
long long cbin()
{
	long long i,step=NMAX;
	for (i=0; step; step>>=1)
		if (!ok(i+step))
			i+=step;
	return ++i;
}
int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	descompunere();//vad factorii primi din descompunerea lui n
	printf("%lld\n",cbin());//caut binar rezultatul
	return 0;
}