#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

vector <int> Divs;

// descompunem N in factori primi
void Divizori(long long N) {

     if (!(N & 1)) {

        Divs.push_back(2);

        while (!(N & 1))
            N >>= 1;
     }

     for (int i = 3; i * i <= N; i += 2) {

        if (N % i == 0) {

            Divs.push_back(i);

            while (N % i == 0)
                N /= i;
        }
    }

    if (N != 1)
        Divs.push_back(N);
}

// numarul de divizori primi ai lui P e maxim 12
// putem folosi principiul includerii si excluderii pentru a numara
// cate fractii ireductibile cu numitorul N sunt
long long Pinex(long long x) {

    int NrBits, sgn = 1, go = (1 << Divs.size());
    long long rez = 0, prod;

    for (int i = 0; i < go; ++i) {

        prod = 1;
        NrBits = 0;
        sgn = 1;

        for (int j = 1, k = 0; j <= i; j <<= 1, ++k) {

            if (i & j) {
                NrBits++;
                prod *= Divs[k];
            }
        }

        if (NrBits & 1)
            sgn = -1;

        rez += sgn * x / prod;
    }

    return rez;
}

long long Bsearch(long long P) {

    long long sol, st = 1, dr = (1LL << 61);

    while (st <= dr) {
        long long mid = st + ((dr - st) >> 1);

        if (Pinex(mid) >= P) {
            sol = mid;
            dr = mid - 1;
        }
        else
            st = mid + 1;
    }

    return sol;
}

int main() {

    long long N, P;

    fin >> N >> P;

    Divizori(N); //scoatem divizorii primi ai lui N

    fout << Bsearch(P); //cautam binar raspunsul

    return 0;
}