#include <cstdio>
#include <cmath>

using namespace std;

const int MAXP=120005;
bool ciur[MAXP];
int primes[50000];

void sieve(void)
{
	int lim=(int)sqrt(1.0 * MAXP);
	for(int i=4;i<=MAXP;i+=2)
		ciur[i]=true;
	for(int i=3;i<=lim;i+=2)
		if(!ciur[i])
			for(int j=i*i;j<=MAXP;j+=2*i)
				ciur[j]=true;
	int k=0;
	for(int i=2;i<=MAXP;i++)
		if(!ciur[i])
			primes[k++]=i;
}

int nrprimes;
long long fact[20];

void prime_fact(long long n)
{
	int i=0;
	int lim=(int)sqrt(1.0 * n);
	nrprimes=0;
	while(n>1 && primes[i]<=lim)
	{
		bool ok=false;
		while(n%primes[i]==0)
		{
			n/=primes[i];
			ok=true;
		}
		if(ok)
		{
			fact[nrprimes++]=primes[i];
			lim=(int)sqrt(1.0 * n);
		}
		i++;
	}
	if(n>1)fact[nrprimes++]=n;
}

long long PINEX(long long x)
{
	long long ans=0;
	int ns=1<<nrprimes;
	for(int i=1;i<ns;i++)
	{
		int c=i;
		long long p=1;
		int nr=0, cardinal=0;
		while(c)
		{
			if(c&1)
			{
				p*=fact[nr];
				cardinal++;
			}
			nr++;
			c>>=1;
		}
		if(cardinal%2==0)ans-=x/p;
		else ans+=x/p;
	}
	ans=x-ans;
	return ans;
}

int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);

    sieve();

	long long N, P;
    scanf("%I64d%I64d", &N, &P);

    prime_fact(N);
    long long left=1, right=1LL<<61;
    while(left<=right)
	{
		long long med=(left+right)/2;
		if(PINEX(med)>=P)
			right=med-1;
		else left=med+1;
	}
	printf("%I64d\n", left);
    return 0;
}