#include <cstdio>
#define ll long long

ll n, p, v[20], t, r;
int l;

void fact(ll n)
{
	int d, c;
	for (d=2; d*d<=n; d++)
	{
		for (c=0; !(n%d); n/=d, c++);
		if (c) v[1+l++]=d;
	}
	if (n>1) v[1+l++]=n;
}

void back(int c, int a, ll p, ll k, int x)
{
	int i;
	if (a>c) t+=k/p; else
	{
		for (i=x+1; i<=l; i++)
			{
				p=p*v[i];
				back(c,a+1,p,k,i);
				p=p/v[i];
			}
	}
}
			
void verif (ll k)
{
	int c, i;
	r=0;
	for (c=1; c<=l; c++)
	{
		t=0;
		back(c,1,1,k,0);
		if (c%2) r+=t; else r-=t;
	}
}

ll caut(ll a, ll b)
{
	ll m;
	int ok, i;
	while (a<=b)
	{
		m=(a-b)/2+b;
		verif(m);
		if (m-r<p) a=m+1; else
		if (m-r>p) b=m-1; else 
		{
			for (i=1, ok=1; i<=l; i++) 
				if (!(m%v[i])) 
				{
					ok=0;
					break;
				}
			if (ok) break; else b=m-1;
		}
	}
	return m;
}
		
	
int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld %lld",&n,&p);
	fact(n);
	printf("%lld",caut(1,1LL<<61));
}