#include <cstdio>
#define LE 100000
#define inf 1LL<<62
#define ll long long
using namespace std;
#include <cmath>
ll i,j,n,P,k,v[LE],N;
ll XOX(ll val)
{
    ll LIM=pow(2,k),P=1,w,t,T,r=0;
    for(i=1; i<LIM; ++i,P=1)
    {
        w=i;
        for(t=1,T=0; w; w/=2,++t)
            if (w%2)P*=v[t],T++;

        if (T%2==0) r-=val/P;
        else r+=val/P;
    }
    return r;
}

ll caut()
{
    ll step=0,poz=0;
    for(  step=1; step<=inf; step*=2);
    for(  poz=0; step; step/=2)
        if (poz+step-XOX(poz+step)<P) poz+=step;
    return poz+1;
}
int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%lld%lld",&n,&P);

    for(i=2,N=n; i*i<n; ++i) if (N%i==0)
        {
            v[++k]=i;
            while (N%i==0) N/=i;
        }
    if (N!=1) v[++k]=N;

    printf("%lld\n",caut());
    return 0;
}