#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 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()
{
	fin>>N>>P;
	fin.close();

	for(register int x=2;(long long)x*(long long)x<=N;++x)
	{
		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;
}