#include <fstream>
using namespace std;

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

long long P, N;
int nrdiv;
long long divi[30];

void prime(long long x)
{
    long long i;
    if(x % 2 == 0)
    {
        divi[++nrdiv] = 2;
        while(x % 2 == 0)
            x /= 2;
    }
    for(i = 3; i * i <= x; i += 2)
        if(x % i == 0)
        {
            divi[++nrdiv] = i;
            while(x % i == 0)
                x /= i;
        }
    if(x > 1)
    {
        divi[++nrdiv] = x;
    }
}
long long nr_fractii_pinex(long long x)
{
    static int K = (1 << nrdiv);
    long long sol = x, prod;
    int nr, p, i, j;
    for(i = 1; i < K; i++)
    {
        prod = 1;
        nr = 0;
        for(j = 0; j < nrdiv; j++)
        {
            if(i & (1 << j))
            {
                prod = 1LL * prod * divi[j + 1];
                nr++;
            }
        }
        if(nr % 2 != 0) p = -1;
        else p = 1;
        sol += 1LL * p * x / prod;
    }
    return sol;
}
void solve()
{
    long long p = 1, u = (1LL << 61), m, sol;
    while(p <= u)
    {
        m = (p + u) / 2;
        if(nr_fractii_pinex(m) < P)
            p = m + 1;
        else
        {
            sol = m;
            u = m - 1;
        }
    }
    g << sol;
}
int main()
{
    f >> N >> P;
    prime(N);
    solve();
    return 0;
}