#include <bits/stdc++.h>

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");
long long n, p, f[102], m;

static inline void Desc(long long n) {
    long long d = 2;
    while(d * d <= n) {
        if(n % d == 0) {
            f[++m] = d;
            while(n % d == 0) n /= d;
        }
        d++;
    }
    if(n > 1) f[++m] = n;
}

static inline long long Prime(long long n) {
    long long red = 0;
    for(long long x = 1; x < (1 << m); x++) {
        long long biti = 0;
        long long p = 1;

        for(long long i = 0; i < m; i++) {
            if(x >> i & 1) {
                p *= f[i + 1];
                biti++;
            }
        }

        if(biti & 1) red += n / p;
        else         red -= n / p;
    }
    return n - red;
}

static inline long long Cb() {
    long long st = 1, dr = INT_MAX;
    long long poz = st;

    while(st <= dr) {
        long long mij = st + (dr - st) / 2;
        long long pr = Prime(mij);

        if(pr >= p) {
            dr = mij - 1;
            poz = mij;
        }
        else st = mij + 1;
    }
    return poz;
}

int main() {
    fin >> n >> p;

    Desc(n);
    fout << Cb();

    return 0;
}