#include<vector>
#include<climits>
#include<fstream>
#include<iostream>
using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

const int NMAX=11e4;
bool p[NMAX+5];
vector<int>dprim;

long long fp[25],nr,mij;
long long i,j;
long long n,k,st,dr,last,val;

void ciur(long long n)
{
	p[0]=p[1]=1;
	for(i=4; i<=n; i+=2)
		p[i]=1;
	for(i=3; i*i<=n; i+=2)
		if(!p[i])
			for(j=i*i; j<=n; j+=i*2)
				p[j]=1;
	dprim.reserve(1e4);
	dprim.push_back(2);
	for(i=3; i<=n; i+=2)
		if(!p[i])
			dprim.push_back(i);
}
void factprimi (long long x )
{
	long long d=0;
	nr =0;
	while(x>1)
	{
		if(x%dprim[d]==0)
        {
            fp[++nr]=dprim[d];
            while(x%dprim[d]==0)
                x/=dprim[d];
        }
		++d;
		if(dprim[d]*dprim[d]<=x && x>1)
		{
		    fp[++nr]=x;
		    x=1;
		}
	}
}
long long pinex(long long x)
{
	long long p,i,j,cnt,r=x;
	for(i=1; i<(1<<nr); ++i)
	{
		p=1;
		cnt=0;
		for(j=0; j<nr; ++j)
			if((1<<j)&i)
			{
				p*=fp[j+1];
				++cnt;
			}
		if(cnt%2==1)
			r=r-x/p;
		else
		    r=r+x/p;
	}
	return r;
}

int main()
{
	ciur(NMAX);
	fin>>n>>k;
	factprimi(n);
	st=0;
	dr=LLONG_MAX;
	while(st<=dr)
	{
		mij=(st+dr)>>1;
		val=pinex(mij);
		if(val>=k)
		{
			dr=mij-1;
			last=mij;
		}
		else
			st=mij+1;
	}
	fout<<last;
	return 0;
}