#include <fstream>
#include <cmath>

using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");
long long ciur[1000005];
long long vecp[1000005],cntp=0;
long long vecf[1000005],cntf=0;
long long sum=0,p;
void ciurul()
{
    ciur[0]=1;
    ciur[1]=1;
    for(long long i=4; i<1000005; i+=2)
        ciur[i]=1;
    for(long long i=3; i*i<1000005; i+=2)
    {
        if(ciur[i]==0)
        {
            for(long long j=i*i; j<1000005; j+=2*i)
                ciur[j]=1;
        }
    }
    cntp=1;
    vecp[cntp]=2;
    for(long long i=3; i<1000005; i+=2)
        if(ciur[i]==0)
            vecp[++cntp]=i;
}
void fprimi(long long m)
{
    long long baza,poz=1;
    baza=vecp[poz++];
    if(m%baza==0)
    {
        while(m%baza==0)
            m/=baza;
        vecf[++cntf]=baza;
    }
    while(baza*baza<=m)
    {
        baza=vecp[poz++];
        if(m%baza==0)
        {
            while(m%baza==0)
                m/=baza;
            vecf[++cntf]=baza;
        }
    }
    if(m>1)
    {
        vecf[++cntf]=m;
    }
//    for(long long i=1; i<=cntf; i++)
//        cout<<vecf[i]<<" ";
//    cout<<'\n';
}
void backt(long long k,long long n,long long prod,long long nr)
{
    if(k==cntf+1)
    {
        if(nr!=1)
            sum+=pow(-1,nr)*(n/prod);
    }
    else
    {
        backt(k+1,n,prod,nr);
        nr++;
        prod*=vecf[k];
        backt(k+1,n,prod,nr);
        nr--;
        prod/=vecf[k];
    }
}
long long solve(long long n)
{
    sum=0;
    backt(1,n,1,1);
    return n-sum;
}
int main()
{
    ciurul();
    long long n;
    cin>>n>>p;
    fprimi(n);
    long long i1=1,i2=pow(2,61),mij=0,rez=0;
    while(i1<=i2)
    {
        mij=(i1+i2)/2;
        long long sol=solve(mij);
        if(sol>p)
        {
            i2=mij-1;
        }
        else if(sol<p)i1=mij+1;
        else
        {
            rez=mij;
            long long sol1=solve(mij-1);
            if(sol1!=sol)
                break;
            i2=mij-1;
        }
    }
    cout<<rez;
    return 0;
}