#include <cstdio>

using namespace std;

bool ciur[150000];
int prim[10000],fact[10000];

inline void Ciur()
{
    int i,j;
    for(i=3;i<400;i+=2)
        if(!ciur[i])
            for(j=i*i;j<=150000;j+=2*i)
                ciur[j]=true;
    prim[++prim[0]]=2;
    for(i=3;i<150000;i+=2)
        if(!ciur[i])
            prim[++prim[0]]=i;
}

inline void Desc(long long N)
{
    int i,d;
    fact[0]=0;
    for(i=1;i<=prim[0] && prim[i]*prim[i]<=N;++i)
    {
        d=prim[i];
        if(N%d==0)
        {
            fact[++fact[0]]=d;
            while(N%d==0)
                N/=d;
        }
    }
    if(N>1)
        fact[++fact[0]]=N;
}

inline long long Solve(long long A)
{
    int i,j,nr,val;
    long long sol=0,prod;
    val=(1<<fact[0]); sol=A;
    for(i=1;i<val;++i)
    {
        nr=0; prod=1;
        for(j=0;j<fact[0];++j)
            if((1<<j)&i)
            {
                ++nr;
                prod=prod*1LL*fact[j+1];
            }
        if(nr%2)
            nr=-1;
        else
            nr=1;
        sol=sol+1LL*nr*A/prod;
    }
    return sol;
}

int main()
{
    long long N,P,st,dr,mij,nr,sol;
    freopen ("frac.in","r",stdin);
    freopen ("frac.out","w",stdout);
    Ciur();
    scanf("%lld%lld", &N,&P);
    Desc(N);
    st=1; dr=100000000000;
    while(st<=dr)
    {
        mij=dr+(st-dr)/2LL;
        nr=Solve(mij);
        if(nr>=P)
        {
            sol=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    printf("%lld\n", sol);
    return 0;
}