#include<cstdio>
using namespace std;
int x;
int d[8];
long long meow(long long n){
    int nr,i,j,m;
    m=1<<x;
    long long p,s=0;
    for(i=0;i<m;i++){
        nr=0;
        p=1;
        for(j=0;j<x;j++)
            if (i&(1<<j)){
                nr++;
                p*=d[j];
            }
        if (nr%2==0)
            s+=(n/p);
        else s-=(n/p);
    }
    return s;
}
int main(){
    freopen ("frac.in","r",stdin);
    freopen ("frac.out","w",stdout);
    long long n,k,i;
    long long in,pas;
    scanf ("%lld%lld",&n,&k);
    if (n==1){
        printf ("%lld",k);
        return 0;
    }
    for(i=2;i*i<=n;i++){
        if (n%i==0){
            d[x]=i;
            x++;
        }
        while(n%i==0) n/=i;
    }
    if (n>1){
        d[x]=n;
        x++;
    }
    in=0;
    pas=(long long)1<<61;
    while(pas>0){
        if (meow(in+pas)<=k) in+=pas;
        pas/=2;
    }
    printf ("%lld",in);
    return 0;
}