#include <fstream>
#include <vector>

using namespace std;

const char InFile[]="frac.in";
const char OutFile[]="frac.out";
const int sqrtMaxN=(int)(1e6)+1;
const long long MAXSOL=1LL<<61;

ifstream fin(InFile);
ofstream fout(OutFile);

long long N,P,sol;
char pciur[sqrtMaxN];
vector<int> nrp;
vector<long long> dp;

inline void ciur()
{
	for(register int i=2;i<sqrtMaxN;++i)
	{
		if(pciur[i]==0)
		{
			nrp.push_back(i);
			for(register int j=i<<1;j<sqrtMaxN;j+=i)
			{
				pciur[j]=1;
			}
		}
	}
}

inline long long pinex(long long NR)
{
	long long sol=0;

	int maxcfg=1<<(dp.size());
	for(register int cfg=1;cfg<maxcfg;++cfg)
	{
		int tcfg=cfg;
		long long prod=1;
		int nrone=0;
		for(register int i=0;tcfg;++i,tcfg>>=1)
		{
			if((tcfg&1)==1)
			{
				++nrone;
				prod*=dp[i];
			}
		}
		if((nrone&1)==1)
		{
			sol+=NR/prod;
		}
		else
		{
			sol-=NR/prod;
		}
	}

	return NR-sol;
}

int main()
{
	//ciur();
	
	fin>>N>>P;
	fin.close();

	for(vector<int>::iterator it=nrp.begin();it!=nrp.end() && (long long)(*it)*(long long)(*it)<=N;++it)
	{
		int x=*it;
		if(N%x==0)
		{
			dp.push_back(x);
			while(N%x==0)
			{
				N/=x;
			}
		}
	}
	if(N>1)
	{
		dp.push_back(N);
	}

	long long st=1;
	long long dr=MAXSOL;
	while(st<=dr)
	{
		long long m=st+((dr-st)>>1);
		if(pinex(m)>=P)
		{
			sol=m;
			dr=m-1;
		}
		else
		{
			st=m+1;
		}
	}

	fout<<sol;
	fout.close();
	return 0;
}