#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 9;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("frac.in");
ofstream fout("frac.out");

const int pmax = 1e6;
bitset<pmax + 5> sieve;
vector<int> primes;
vector<int> factors;
ll b, p;

void precomputing() {
    sieve.set();
    for (int i = 2; i <= pmax; ++i) {
        if (sieve[i]) {
            primes.push_back(i);
            for (ll j = 1ll * i * i; j <= pmax; j += i) {
                sieve[j] = 0;
            }
        }
    }
}

ll check(ll a) {
    ll cnt = 0;
    for (int mask = 0; mask < (1 << factors.size()); ++mask) {
        ll divisor = 1;
        for (int i = 0; i < mask; ++i) {
            if ((mask >> i) & 1) {
                divisor *= -factors[i];
            }
        }
        cnt += a / divisor;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    precomputing();
    fin >> b >> p;
    for (auto& p : primes) {
        if (b / p / p < 1) {
            break;
        }
        if (b % p == 0) {
            factors.push_back(p);
            while (b % p == 0) {
                b /= p;
            }
        }
    }
    if (b > 1) {
        factors.push_back(b);
    }
    ll st = 1, dr = 1ll << 62, ans = 0;
    while (st <= dr) {
        ll mid = st + (dr - st) / 2;
        if (check(mid) >= p) {
            ans = mid, dr = mid - 1;
        }
        else {
            st = mid + 1;
        }
    }
    fout << ans;
}