#include <fstream>
using namespace std;
ifstream in("frac.in");
ofstream out("frac.out");
int prime[12],cnt1;
long long p,n;
void desc(long long n)
{
    int d=2,cnt;
    while(d*d<=n)
    {
        cnt=0;
        if(n%d==0)
        {
            n/=d;
            cnt++;
        }
        if(cnt)
            prime[++cnt1]=d;
        d++;
    }
    if(n!=1)
        prime[++cnt1]=n;
}
long long pinex(long long n)
{
    long long i,cate=n,cnt,prod,j;
    for(i=1; i<(1<<cnt1); i++)
    {
        cnt=0;
        prod=1;
        for(j=0; j<=cnt1-1; j++)
            if((1<<j)&i)
            {
                cnt++;
                prod=(long long)(prod*prime[j+1]);
            }
        if(cnt%2==1)
            cate-=n/prod;
        else
            cate+=n/prod;
    }
    return cate;
}
void cautbin()
{
    unsigned long long r=0,pas=1ULL<<61;
    while(pas)
    {
        if(pinex(r+pas)<=p)
            r+=pas;
        pas/=2;
    }
    out<<r+1;
}
int main()
{
    in>>n>>p;
    desc(n);
    cautbin();
    return 0;
}