#include <fstream>

using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

int prime[12],nr;
long long p,n;

void desc(long long n)
{
    int d=2,cnt;
    while(d*d<=n)
    {
        cnt=0;
        while(n%d==0)
        {
            n/=d;
            cnt++;
        }
        if(cnt)prime[++nr]=d;
        d++;
    }
    if(n!=1)prime[++nr]=n;

}

long long verif(long long n)
{
    long long i,s=n,cnt,p,j;
    for(i=1;i<(1<<nr);i++)
    {
        cnt=0;
        p=1;
        for(j=0;j<=nr-1;j++)
            if((1<<j)&i)
            {
                cnt++;
                p=(long long)(p*prime[j+1]);
            }
        if(cnt%2)s-=n/p;
        else
            s+=n/p;
    }
    return s;
}
void cbin()
{
    unsigned long long r=0,st=1,dr=1ULL<<61,mij;

    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(verif(mij)<p)st=mij+1;
        else dr=mij-1;
    }
    g<<st;
}
int main()
{
    f>>n>>p;
    desc(n);
    cbin();
    return 0;
}