#include <cstdio>
#include <vector>
using namespace std;

long long N, P;
vector <int> V;

void Fact()
{
    long long f = 2, n = N;
    
    while(n != 1)
    {
        int ok = 0;
        while(!(n % f)) { n /= f; ok = 1; }
        
        if(ok) V.push_back(f);
        ++ f;
    }
}

long long Compute(long long n)
{
    int i, j, sz = V.size();
    long long ret = n;
    
    for ( i = 1; i < (1<<sz); ++i )
    {
        long long p = 1;
        int s = 1;
        
        for ( j = 0; j < sz; ++j )
            if((i>>j) & 1)
            {
                s *= -1;
                p *= V[j];
            }
            
        ret += (n / p) * s;
    }
    
    return ret;
}

int main()
{
    freopen("frac.in", "rt", stdin);
    freopen("frac.out", "wt", stdout);
    
    scanf("%lld %lld", &N, &P);
    Fact();

    long long step = (long long) 1 << 61;
    long long i;
    
    for ( i = 0; step; step >>= 1 )
        if(Compute(i + step) < P) i += step;
    
    printf("%lld", i+1);
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}