#include <fstream>
#include <cmath>

using namespace std;

const long long INF= 0x4000000000000000, NMAX= 1000000, P_MAX= 200000;

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

long long p[P_MAX + 1], pr[P_MAX + 1], pr_count = 0;;
bool ciur[NMAX + 3];

void ciurul ()
{
    long long lim = 1000;
    for (int i = 4; i <= NMAX; i += 2)
    {
        ciur[i] = 1;
    }

    for (int i = 3; i <= lim; i += 2)
    {
        if (!ciur[i])
        {
            for (int j = i*i; j <= NMAX; j += 2 * i) ciur[j] = 1;
        }
    }

    pr[++pr_count] = 2;

    for (int i = 3; i <= NMAX; i += 2)
    {
        if (!ciur[i])  pr[++pr_count] = i;
    }
}

long long Desc_factori(long long N)
{
    long long R = 0, ind = 1, lim = (long long)sqrt(1.0*N);
    bool ok = 0;

    while (N>1 && pr[ind] <= lim)
    {
        ok = 0;
        while ( N%pr[ind] == 0 )
        {
            N /= pr[ind];
            ok = 1;
        }
        if (ok)
        {
            p[++R] = pr[ind];
            lim = (long long)sqrt(1.0*N);
        }
        ++ind;
    }

    if (N>1)
    {
        p[++R] = N;
    }

    return R;
}


long long PINEX(long long X, long long Y)
{
    long long Sol = 0, nr= Desc_factori(Y),  k = 1 << nr;

    for ( long long i = 1; i<k; ++i )
    {
        long long cnt = 0, prod = 1;
        for ( long long j = 0; j<nr; ++j )
        {
            if (i & (1 << j))
            {
                ++cnt;
                prod *= p[j + 1];
            }
        }
        if (cnt % 2 == 1)
        {
            Sol += X / prod;
        }
        else
        {
            Sol -= X / prod;
        }
    }
    return X - Sol;
}

int main()
{
    ciurul();

    long long Y, P;
    in >> Y >> P;

    long long step = INF, i= INF;

    for (; step; step >>= 1)
    {
        if ( i-step>=0 && PINEX(i - step, Y)>=P  )  i -= step;
    }

    out << i << '\n';

    return 0;
}