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

using int64 = long long;

int64 N, P;
vector<int64> primes;

// numarul de valori <= x coprime cu N
int64 coprimeCount(int64 x) {
    int k = primes.size();
    int64 bad = 0;

    for (int mask = 1; mask < (1 << k); mask++) {
        int bits = 0;
        int64 prod = 1;

        for (int i = 0; i < k; i++) {
            if (mask & (1 << i)) {
                bits++;
                if (prod > x / primes[i]) {
                    prod = x + 1;
                    break;
                }
                prod *= primes[i];
            }
        }

        if (prod > x) continue;

        if (bits & 1)
            bad += x / prod;
        else
            bad -= x / prod;
    }

    return x - bad;
}

int main() {
    cin >> N >> P;

    int64 temp = N;
    for (int64 d = 2; d * d <= temp; d++) {
        if (temp % d == 0) {
            primes.push_back(d);
            while (temp % d == 0)
                temp /= d;
        }
    }
    if (temp > 1)
        primes.push_back(temp);

    int64 st = 1, dr = max<int64>(1, P * N);

    while (st < dr) {
        int64 mid = (st + dr) / 2;
        if (coprimeCount(mid) >= P)
            dr = mid;
        else
            st = mid + 1;
    }

    cout << st;
    return 0;
}