#include <fstream>

using namespace std;

long long int N,P,Aux,k,Mij,St,Dr,Rez,j,i,Prod,Nr,Nrtot,Fact[1001],Pmax;

int main()
{
    ifstream fin("frac.in");
    ofstream fout("frac.out");

    fin>>N>>P;
    Aux=N;
    k=0;
    for(i=2;i<=N and Aux>1;i++)
        if(Aux%i==0)
        {
            while(Aux>1 and Aux%i==0)
                Aux=Aux/i;
            k++;
            Fact[k]=i;
        }//if
    //fout<<k<<'\n';
    St=1;
    Dr=(long long)1<<61;
    while(St<=Dr)
    {
        Mij=(St+Dr)/2;
        Pmax=(1<<k)-1;
        Nrtot=0;
        for(i=1;i<=Pmax;i++)
        {
            Nr=0;
            Prod=1;
            for(j=0;j<=k-1;j++)
                if(((1<<j) & i)!=0)
                {
                    Nr++;
                    Prod=Prod*Fact[j+1];
                }//if
            if(Nr%2==1)
                Nrtot+=Mij/Prod;
            else
                Nrtot-=Mij/Prod;
        }//for i
        if(Mij-Nrtot<P)
            St=Mij+1;
        else
        {
            Dr=Mij-1;
            Rez=Mij;
        }//else
    }//while
    fout<<Rez;

    fin.close ();
    fout.close();
    return 0;
}