#include <bits/stdc++.h>

using namespace std;

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

long long int n, p, v[50];
bitset<50> f;
int k;

long long int fr(long long int x) {
    long long int nr = 0;
    f.reset();
    while(!f[0]) {
        int i = k;
        while(f[i]) {
            f[i] = false;
            i--;
        }
        f[i] = true;
        long long int prod = 1LL, cnt = 0;
        for(int i = 1; i <= k; i++) {
            if(f[i]) {
                prod *= v[i];
                cnt++;
            }
        }
        if(prod != 1) {
            if(cnt % 2 == 0) {
                nr -= x / prod;
            } else {
                nr += x / prod;
            }
        }
    }
    x = (nr > 0 ? x - nr : x + nr);
    return x;
}

int main() {
    fin >> n >> p;
    fin.close();
    long long int x = n, d = 2;
    while(x > 1) {
        long long int P = 0;
        while(x % d == 0) {
            x /= d;
            P++;
        }
        if(P != 0) {
            v[++k] = d;
        }
        d++;
        if(d * d > x) {
            d = x;
        }
    }
    long long int st = 1, dr = (1LL << 61);
    while(st <= dr) {
        long long int mid = (st + dr) / 2;
        if(fr(mid) >= p) {
            dr = mid - 1;
        } else {
            st = mid + 1;
        }
    }
    fout << st;
    return 0;
}