#include<bits/stdc++.h>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
vector<long long>primi;
long long n,poz;
long long pinex(long long a) {
    long long k=primi.size();
    long long rsp=0;
    for(long long mask=1; mask<((long long)1<<k); mask++) {
        long long nr=0,p=1;
        for(long long j=0; j<k; j++) {
            if(mask&((long long)1<<j)) {
                nr++;
                p*=primi[j];
            }
        }
        if(nr%2==0) {
            rsp-=a/p;
        } else {
            rsp+=a/p;
        }
    }
    return a-rsp;
}
void fact(long long nr) {
    long long d=2;
    while(nr>1) {
        bool ok=0;
        while(nr%d==0) {
            nr/=d;
            ok=1;
        }
        if(ok) {
            primi.push_back(d);
        }
        d++;
        if(d*d>nr) {
            d=nr;
        }
    }
}
int main() {
    fin>>n>>poz;
    fact(n);
    long long st=0,dr=((long long)1<<61)+1;
    while(dr-st>1) {
        long long mid=(st+dr)/2;
        if(pinex(mid)<poz) {
            st=mid;
        } else {
            dr=mid;
        }
    }
    fout<<dr;
    return 0;
}