#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");
long long i, j, n, m, k, d, produs, nr, raspuns, a, b, t, kk, st, dr, p, mid;
long long v[1000002];
bool f[1000002];
long long caut(long long a){
    memset(f, 0, sizeof(f));
    long long raspuns=0;
    while(f[0]==0){
        long long i=nr;
        while(f[i]==1)
            f[i]=0, i--;
        if(i==0)
            break;
        f[i]=1;
        long long val=0;
        long long produs=1;
        for(long long i=1;i<=nr;i++){
            if(f[i]==1){
                produs*=v[i];
                val++;
            }
        }
        if(val%2)
            raspuns+=a/produs;
        else
            raspuns-=a/produs;
    }
    raspuns=a-raspuns;
  //  cout<<raspuns<<" "<<a<<"\n";
    return raspuns;

}
int main() {
    cin>>n>>p;
    d=2;
    m=n;
    while(m!=1){
        if(m%d==0){
            v[++nr]=d;
            while(m%d==0)
                m/=d;
        }
        d++;
        if(d*d>m && m!=1)
            d=m;
    }
    st=1;
    dr=(1LL<<61);
    while(st<=dr){
        mid=(st+dr)/2;
        if(caut(mid)>=p)
            dr=mid-1;
        else
            st=mid+1;
    }
    cout<<st;
}