#include <stdio.h>

const long long ls=1LL<<61;
//const long long ls=40;
long long n, p;
long fact[100];
int nrFactori;

long long factPrimi(long long n);
long long f(long long x);
void submultimi(int a, long long &sol, long long x);
void calcul(int st[100], long long &sol, long long x);
long long cautaBin(long long li, long long ls);

int main()
{
	long long rez;
	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w", stdout);
	scanf("%lld%lld", &n, &p);
	nrFactori=factPrimi(n);
	rez=cautaBin(1, ls);
	printf("%lld", rez);
	return 0;
}//main

long long factPrimi(long long n)
{
	long long divizor=3;
	int poz=0;
	if ((n%2)==0)
	{
		fact[poz++]=2;
		while ((n%2)==0)
			n/=2;		
	}//if
	while (n>1)
	{
		if ((n%divizor)==0)
		{
			fact[poz++]=divizor;
			while ((n%divizor)==0)
				n/=divizor;
		}//if
		divizor+=2;
	}//while
	return poz;
}//factPrimi

long long f(long long x)//nr de nr prime cu n <= x
{
	long long sol=x;
	int i;
	for (i=0; i<nrFactori; i++)
		sol-=x/fact[i];
	submultimi(nrFactori, sol, x);
	return sol;
}//f

void submultimi(int a, long long &sol, long long x)
{
	int st[100];
	int k=0;
	st[k]=-1;
	while (k>=0)
	{
		if (st[k]<1)
		{
			st[k]++;
			if (k==(a-1))
				calcul(st, sol, x);
			else
				st[++k]=-1;
		}//if
		else
			--k;
	}//while
}//submultimi

void calcul(int st[100], long long &sol, long long x)
{
	long long i, t=1;
	int cont=0;
	for (i=0; i<nrFactori; i++)
		if (st[i])
		{
			t*=fact[i];
			cont++;
		}//if
	if (cont>1)
	  sol+=x/t;
}//calcul

long long cautaBin(long long li, long long ls)
{
	long long lm;
	while (li<ls)
	{
		lm=(li+ls)/2;
		if (p<=f(lm))
			ls=lm;
		else
			li=lm+1;
	}//while
	lm=(li+ls)/2;
	if (f(lm)<p)
		lm++;
	return lm;
}//cautaBin