# include <fstream>
# define DIM 320000
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long b[20],d[20],n,nr,i,j,k,sol,p,cnt,step;
int main () {
    fin>>n>>nr;
    for(i=2;i*i<=n;i++){
        if(n%i==0){
            d[++k]=i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n!=1)
        d[++k]=n;
    for(step=(1LL<<60),j=0;step;step/=2){
        n=j+step;
        sol=0;
        b[0]=0;
        while(b[0]==0){
            i=k;
            while(b[i]){
                b[i]=0;
                i--;
            }
            b[i]=1;
            p=1;
            cnt=0;
            for(i=1;i<=k;i++)
                if(b[i]){
                    p*=d[i];
                    cnt++;
                }
            if(cnt%2==0)
                sol+=n/p;
            else
                sol-=n/p;
        }
        if(sol<nr)
            j+=step;
    }
    fout<<j+1<<"\n";
    return 0;
}