#include <cstdio>
#include <vector>

using namespace std;

#define LL long long

vector < LL > div;
LL where,left=2,right=1e18,mid,N,P;


void get_divs(LL X)
{
    LL i,current;

    for (i=2;i*i<=X && X>1;++i)
    {
        current=0;

        while (X%i==0)
        {
            X/=i;
            ++current;
        }

        if (current)
        div.push_back(i);
    }

    if (X>1)
    div.push_back(X);
}

LL find(LL value)
{
    LL current=0,one,mask,j,f;

    for (mask=1;mask<(1<<div.size());++mask)
    {
        one=0;
        f=value;

        for (j=0;j<div.size();++j)
        if (mask&(1<<j))
        ++one,f/=div[j];

        current+=(one&1) ? f : -f;
    }

    return value-current;
}

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

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

get_divs(N);

while (true)
{
    mid=(left+right)>>1;

    where=find(mid);

    if (left>right)
    {
        printf("%lld\n",left);
        return 0;
    }

    (where>=P) ? right=mid-1 : left=mid+1;
}

return 0;
}