#include <cstdio>
#include <vector>

using namespace std;

long long N, P;

vector <long long> F;

void Fact()
{
    long long f = 2;
    long long n = N;

    while(n != 1)
    {
        int ok = 0;
        while(!(n % f))
        {
            n /= f;
            ok = 1;
        }
        if(ok) F.push_back(f);

        ++ f;
    }
}

long long Fn(long long x)
{
    long long i, j, r = x, n = F.size();

    for(i=1; i<(1 << n); ++i)
    {
        long long p = 1;
        long long s = 1;

        for(j=0; j<n; ++j)
            if((i >> j) & 1)
            {
                s *= -1;
                p *= F[j];
            }

        r += (x / p) * s;
    }

    return r;
}

int main()
{
    freopen("frac.in", "rt", stdin);
    freopen("frac.out", "wt", stdout);

    scanf("%lld %lld", &N, &P);
    Fact();

    long long i = 0, step = (long long) 1 << 61;

    for(; step; step>>=1)
        if(Fn(i+step) < P) i += step;

    printf("%lld", i + 1);

    fclose(stdin);
    fclose(stdout);

    return 0;
}