#include <stdio.h>
#define LMax 110010
#define PMax 11010
typedef long long ll;
const char IN[]="frac.in",OUT[]="frac.out";

ll N,P;
int p[PMax];
int a[PMax];

void ciur()
{
	int i,j;
	static bool b[LMax];
	for (i=2;i<LMax;++i) if (!b[i])
	{
		p[++p[0]]=i;
		if (i<500)
		for (j=i*i;j<LMax;j+=i) b[j]=true;
	}
}

void prepare(ll A)
{
	int i;
	for (i=1;p[i]*p[i]<=A;++i) if (A%p[i]==0)
	{
		a[++a[0]]=p[i];
		while (A%p[i]==0) A/=p[i];
	}
	if (A!=0) a[++a[0]]=A;
}

ll cmmdc(ll a,ll b){
	ll r;
	while (b)
		b=(r=a%b,a=b,r);
	return a;
}

ll cmmmc(ll a,ll b){
	return a*b/cmmdc(a,b);
}

ll number(ll L)
{
	int i,mask,cnt;
	ll c,ret=0;

	for (mask=1;mask<(1<<a[0]);++mask)
	{
		c=1;cnt=0;
		for (i=0;i<a[0] && c<=L;++i) if ((1<<i)&mask)
			c=cmmmc(c,a[i+1]),++cnt;
		if (cnt&1)
			ret+=L/c;
		else
			ret-=L/c;
	}
	return L-ret;
}

ll search(ll L)
{
	ll i,step;
	for (step=1;step<=L;step<<=1);
	for (i=L;step;step>>=1)
		if (i-step>0 && number(i-step)>=P)
			i-=step;
	return i;
}

int main()
{
	int i;
	freopen(IN,"r",stdin);
	scanf("%lld%lld",&N,&P);
	fclose(stdin);

	ciur();
	prepare(N);

	freopen(OUT,"w",stdout);
	printf("%lld\n",search(1LL<<61));
	fclose(stdout);

	return 0;
}