#include <fstream>
/*
calc vectorul dp[i] = al i-lea div prim al lui n
generezi toate submultimile multimii clor np div primi ai lui n
for (i = 0; i < (1<<np); i++){
    for (j = 0; j < np; j++)
        if (i & (1<<j))
            j apartine multimii i

ex: n = 2 => dp=(2,3)
submultimile:
x=20
0 -> multimii vide
1 -> {2} -> -20/2
2 -> {3} -> -20/3
3 -> {2,3} -> +20/6
nr prime cu 12 mai mici ca 20: 20 - 20/2 - 20/3 + 20/6 = 7
*/

using namespace std;

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

long long d[11];
int nrprime;

long long f(long long nr)
{
    int i, j, nc;
    long long sum, prod;

    sum = 0;
    for(i = 0; i < (1 << nrprime); i++)
    {
        nc = 0;
        prod = 1;
        for(j = 0; j < nrprime; j++)
            if(i & (1 << j))
            {
                nc++;
                prod *= d[j + 1];
            }

        if(nc % 2)
            sum -= nr/prod;
        else
            sum += nr/prod;
    }

    return sum;
}

int main()
{
    long long n, prim, i, pas, p;

    in>>n>>p;

    prim = 2;
    nrprime = 0;
    if(n % prim == 0)
    {
        nrprime++;
        d[nrprime] = prim;
        while(n % prim == 0)
            n /= prim;
    }

    prim = 3;
    while(prim * prim <= n)
    {
        if(n % prim == 0)
        {
            nrprime++;
            d[nrprime] = prim;
            while(n % prim)
                n /= prim;
        }
        prim += 2;
    }
    if(n != 1)
    {
        nrprime++;
        d[nrprime] = n;
    }

    i = 0;
    pas = (long long)1 << 61;
    while(pas)
    {
        if(f(i + pas) < p)
            i += pas;
        pas /= 2;
    }
    out<<i + 1<<'\n';
    return 0;
}