#include <fstream>
#include <vector>

using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

long long n, p, num;
vector<long long> v;

void desc(long long x)
{
    long long d = 2;
    while(x > 1)
    {
        long long p = 0;
        while(x % d == 0)
            x /= d, p ++;

        if(p)
            v.push_back(d);

        d ++;
        if(d * d > x)
            d = x;
    }
}

long long nrprime(long long x)
{
    long long ans = 0;
    for(long long i = 1; i < (1LL<<v.size()); i ++)
    {
        long long nr = 0, div = 1;
        for(long long j = 0; j < v.size(); j ++)
            if((1LL<<j)&i)
                nr ++, div *= v[j];

        if(nr % 2 == 0)
            ans -= x / div;
        else
            ans += x / div;
    }

    return x - ans;
}

int main()
{
    f >> n >> p;
    desc(n);

    long long st = 1, dr = (1LL<<61);
    while(st <= dr)
    {
        long long mij = (st + dr) / 2;
        if(nrprime(mij) >= p)
            num = mij, dr = mij - 1;
        else
            st = mij + 1;
    }

    g << num;
    return 0;
}