#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("frac.in");
ofstream fout("frac.out");
#include <bits/stdc++.h>
#define endl '\n'
#endif

#define int int64_t

const int MAXVAL = 1e6+5;

int n, p;
bool ciur[MAXVAL];
vector<int> primes;
int fact[2000];

void precalc() {
    for (int i = 2; i < MAXVAL; i++) {
        if (!ciur[i]) {
            for (int j = 2 * i; j < MAXVAL; j += i) {
                ciur[j] = 1;
            }
            primes.push_back(i);
        }
    }
}

void read() {
    fin >> n >> p;
}

int get_fact(int n) {
    int cnt = 0, e = -1;
    while (n != 1) {
        e++;
        if (n % primes[e] == 0) {
            fact[++cnt] = primes[e];
            while (n % primes[e] == 0) {
                n /= primes[e];
            }
        }
        if (primes[e] * primes[e] > n && n != 1) {
            fact[++cnt] = n;
            n = 1;
        }
    }
    return cnt;
}

int verif(int a, int b) {
    int fcnt = get_fact(b);
    int ans = 0;
    for (int i = 1; i <= (1 << fcnt); i++) {
        int cnt = 0, p = 1;
        for (int j = 0; j < fcnt; j++) {
            if (i & (1 << j)) {
                p *= fact[j + 1];
                cnt++;
            }
        }
        if (cnt % 2 == 0) ans += a / p;
        else ans -= a / p;
    }
    return ans;
}

int solve() {
    int l = 1;
    int r = 1e14+5;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (verif(mid, n) < p)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return r + 1;
}

int32_t main() {
    precalc();
    read();
    fout << solve();
    return 0;
}