#include <bits/stdc++.h>

using namespace std;

#define STDIO 0
#if STDIO
    #define fin cin
    #define fout cout
#else
    ifstream fin("frac.in");
    ofstream fout("frac.out");
#endif  // STDIO

vector<long long> fact;
long long n, p;

static inline void GetFact(long long n) {
    long long d = 2;
    while(d * d <= n) {
        if(n % d == 0) {
            fact.push_back(d);
            while(n % d == 0) n /= d;
        }
        d++;
    }
    if(n > 1) fact.push_back(n);
}

static inline long long CmmdcCom(long long n) {
    long long reduct = 0;
    for(long long x = 1; x < (1 << fact.size()); x++) {
        long long nrBiti = 0;
        long long prod = 1;

        for(long long i = 0; i < fact.size(); i++) {
            if(x >> i & 1) {
                prod *= fact[i];
                nrBiti++;
            }
        }

        if(nrBiti & 1) reduct += n / prod;
        else           reduct -= n / prod;
    }
    return reduct;
}

int main() {
    if(STDIO) ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> p;
    GetFact(n);

    long long st = 1, dr = 1e17 + 7;
    long long poz = st;

    while(st <= dr) {
        long long mij = st + (dr - st) / 2;
        long long pr = mij - CmmdcCom(mij);

        if(pr >= p) {
            dr = mij - 1;
            poz = mij;
        }
        else st = mij + 1;
    }
    fout << poz;

    return 0;
}