#include <cstdio>
#include <vector>

using namespace std;

vector<long long> div;
long long pos,st=2,dr=1000000000000,mij,n,p;

void divizori(long long X)
{
    long long i,crt;
    for (i=2;i*i<=X && X>1;++i)
    {
        crt=0;
        while (X%i==0)
        {
            X/=i;
            ++crt;
        }
        if (crt)
        div.push_back(i);
    }
    if (X>1)
    div.push_back(X);
}

long long caut(long long valeur)
{
    long long crt=0,bit,jim_carrey,j,ans;
    for (jim_carrey=1;jim_carrey<(1<<div.size());++jim_carrey)
    {
        bit=0;
        ans=valeur;
        for (j=0;j<div.size();++j)
        if (jim_carrey&(1<<j))
        ++bit,ans/=div[j];
        crt+=(bit&1) ? ans : -ans;
    }
    return valeur-crt;
}

int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%lld%lld",&n,&p);
    divizori(n);
    while (1)
    {
        mij=(st+dr)>>1;
        pos=caut(mij);
        if (st>dr)
        {
            printf("%lld\n",st);
            return 0;
        }
        if (pos>=p)
        {
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    return 0;
}