#include <cstdio>
#define llt long long
#define FMax 12

llt v[FMax+1];
llt P,mid,ans;

void back(int k, llt M, int nr)
{
    if( k == v[0]+1 )
    {
        if(nr%2) ans = ans + mid/M;
        else if(nr) ans = ans - mid/M;
        return;
    }
    back(k+1,M*v[k],nr+1);
    back(k+1,M,nr);
}

bool is_good()
{
    ans = 0;
    back(1,1,0);
    if( mid-ans >= P ) return 1;
    return 0;
}

int main(){
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);

    llt N,st,dr,f;

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

    for(int i = 2; i*i <= N; ++i)
    if( N % i == 0 )
    {
        v[ ++v[0] ] = i;
        while( N % i == 0 ) N /= i;
    }
    if( N > 1 ) v[ ++v[0] ] = N;

    for( f = 0, st = 1, dr = 1LL<<61; st <= dr; )
    {
        mid = (st+dr)/2;
        if( is_good() ) dr = mid-1;
        else { f = mid; st = mid+1; }
    }

    printf("%lld\n",f+1);



return 0;
}