#include <fstream>

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

typedef long long ll;

ll n;
ll v[105],y=0;
int cnt=0;

ll val;
ll ans=0;

void bkt(int strat,int l,ll prod) {
    if(strat==y) {
        if(l%2==0)
            ans+=val/prod;
        else
            ans-=val/prod;
    }
    else {
        bkt(strat+1,l,prod);
        bkt(strat+1,l+1,prod*v[strat+1]);
    }
}

ll f(ll x) {
    val=x;
    ans=0;
    bkt(0,0,1);
}

ll cate;

int main() {
    fin>>n>>cate;
    cnt=0;
    while(n%2==0) {
        n/=2;
        cnt++;
    }
    if(cnt)
        v[++y]=2;
    ll d=3;
    while(d*d<=n) {
        cnt=0;
        while(n%d==0) {
            n/=d;
            cnt++;
        }
        if(cnt)
            v[++y]=d;
        d+=2;
    }
    if(n>1)
        v[++y]=n;
    ll r=0,pas=(1LL<<60);
    while(pas) {
        f(r+pas);
        if(ans<cate)
            r+=pas;
        pas/=2;
    }
    r++;
    return 0;
}