#include<stdio.h>
long long div[15],sol;
long long x;
void apel(long long n,long long i){
    long long nr=0,p=1,pas=0;
    while(i){
        if(i&1){
            p*=div[pas];
            ++nr;
        }
        i>>=1;
        ++pas;
    }
    if(nr&1)
        sol-=n/p;
    else
        sol+=n/p;
}
long long f(long long n){
    long long i;
    sol=n;
    for(i=1;i<(1<<x);++i)
        apel(n,i);
    return sol;
}
void solve(long long p){
    long long inf=1,sup=2,mij;
    for(mij=1;mij<61;++mij)
        sup*=2;
    sup+=10000;
    sup=(long long)1<<(long long)61;
    while(inf<sup){
        mij=(inf+sup)>>1;
        if(f(mij)>=p)
            sup=mij;
        else
            inf=mij+1;
    }
     
    printf("%lld\n",sup);
}
void diviz(long long n){
    long long i;
    if(n&1)
        x=-1;
    else{
        div[0]=2;
        while(n%2==0)
            n>>=1;
    }
    for(i=3;i*i<=n;++i){
        if(n%i==0){
            div[++x]=i;
            for(;!(n%i);n/=i)
                ;
        }
    }
    if(n>1)
        div[++x]=n;
    ++x;
}
int main(){
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    long long n,p;
    scanf("%lld%lld",&n,&p);
    diviz(n);
    solve(p);
     
    fclose(stdin);
    fclose(stdout);
    return 0;
}