#include <bits/stdc++.h>
using namespace std;

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

vector<long long> divi;

long long pinex(long long mij){
    long long ans = 0, cnt, i, j;

    for(i = 1; i < (1 << divi.size()); i++){ // Bit Mask-ul
        cnt = 1;
        for(j = 0; j < divi.size(); j++){ // 2 ^ j = bit-ul
            if(i & (1LL << j)){ // Verificam daca este prezent in bit mask-ul curent
                cnt *= divi[j];
            }
        }

        if(__builtin_popcount(i) & 1){
            ans += mij / cnt;
        } else {
            ans -= mij / cnt;
        }
    }
    return mij - ans;
}

int main() {
    long long n, p, d, st, dr, mij;

    fin >> n >> p;

    d = 2;
    while (d * d <= n) {
        if (n % d == 0) {
            do {
                n /= d;
            } while (n % d == 0);
            divi.push_back(d);
        }
        ++d;
    }
    if(n > 1){
        divi.push_back(n);
    }

    st = 1, dr = (1LL << 61);
    while(st <= dr){
        mij = (st + dr) >> 1;

        if(pinex(mij) < p){
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }

    fout << ++dr;
    return 0;
}