#include <stdio.h>
#define N 1<<7
#define NMAX 1<<61
long long n,p,r,sum;
long long v[N];
char stiva[N];
void descompunere()
{
	long long i;
	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;
}
void back(long long k,long long factori,long long x)
{
	if (k==r+1)
	{
		if (factori==0)
			return;
		long long i,prod=1;
		for (i=1; i<=r; i++)//formez numere
			if (stiva[i])
				prod*=v[i];
		if (factori&1)
			sum+=x/prod;
		else
			sum-=x/prod;
		return;
	}
	stiva[k]=0;back(k+1,factori,x);
	stiva[k]=1;back(k+1,factori+1,x);
}
inline int ok(long long x)//principiul includerii si excluderii
{
	long long rez=x;
	sum=0;
	back(1,0,x);//formez toate nr posibile
	rez-=sum;
	if (rez>=p)
		return 1;
	return 0;
}
long long cbin()
{
	long long i,step=(long long)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;
}