#include <fstream>

using namespace std;
ifstream in ("frac.in");
ofstream out ("frac.out");
int p[30],k,pr;
void descmp (long long n)
{
    for(int i=2;i*i<=n;++i)
    {
        if(n%i==0)
        {
            p[++k]=i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n!=1)
        p[++k]=n;
}
unsigned long long pinex (unsigned long long val)
{
    unsigned long long s=0,ci,x=1<<k,cnt,i,prod,j;
    for(i=0;i<x;++i)
    {
        prod=j=1;
        ci=i;
        cnt=0;
        while(ci)
        {
            if(ci%2==1){
                cnt++;
            prod=prod*p[j];
            }
            j++;
            ci/=2;
        }
        if(cnt%2==0)
            s+=val/prod;
        else
            s-=val/prod;
    }
    return s;
}
void cautbin ()
{
    unsigned long long pas=1ULL<<61,k=0;
    while(pas)
    {
        if(pinex(k+pas)<pr)
            k+=pas;
        pas/=2;
    }
    out<<k+1;
}
int main()
{
    long long n;
    in>>n>>pr;
    descmp(n);
    cautbin();
    return 0;
}