#include<fstream>
#define INF 1ll<<62
#define ll long long
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
ll i,n,p,nrd,li,ls,mij,sol,v[100];
ll rez(ll x)
{
    ll sol=x,i,j,dld=1<<nrd,nr,p;
    for(i=1;i<dld;++i)
    {
        nr=0;
        p=1;
        for(j=0;j<nrd;++j)
        if(i&(1<<j))
        {
            ++nr;
            p*=v[j+1];
        }
        if(nr%2)
        nr=-1;
        else
        nr=1;
        sol+=nr*(x/p);
    }
    return sol;
}
int main()
{
    f>>n>>p;
    for(i=2;i*i<n&&n>1;++i)
    if(n%i==0)
    {
        ++nrd;
        v[nrd]=i;
        while(n%i==0)
        n/=i;
    }
    if(n>1)
    ++nrd,v[nrd]=n;
    li=1;
    ls=INF;
    while(li<=ls)
    {
        mij=(li+ls)/2;
        if(rez(mij)>=p)
        {
            ls=mij-1;
            sol=mij;
        }
        else
        li=mij+1;
    }
    g<<sol<<'\n';
    return 0;
}