#include <fstream>
#include <vector>

using namespace std;

long long N, P;
long long fact[20], numbs[4000];
bool sign[4000];

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

    fin >> N >> P;

    for (long long i = 2; i * i <= N; ++i)
    {
        if (N % i == 0)
        {
            fact[++fact[0]] = i;
            while (N % i == 0)
                N /= i;
        }
        if (i != 2) ++i;
    }

    if (N != 1) fact[++fact[0]] = N;

    for (long long i = 1; i < (1LL << fact[0]); ++i)
    {
        long long factnow = 1;
        for (int j = 0; j < fact[0]; ++j)
            if ((i & (1 << j)) != 0)
                factnow *= fact[j + 1];

        long long nrb = 0, aux = i;
        while (aux) ++nrb, aux &= aux - 1;

        numbs[++numbs[0]] = factnow * ((nrb & 1) ? 1 : -1);
    }

    long long step = 1LL << 61, result = 0;
    for (; step; step >>= 1)
        if (result + step <= (1LL << 61))
        {
            long long times = 0;
            for (int i = 1; i <= numbs[0]; ++i)
                times += (result + step) / numbs[i];
            times = (result + step) - times;

            if (times < P)
                result += step;
        }

    ++result;
    fout << result;

    fin.close();
    fout.close();
}