#include <iostream>
#include <fstream>
#include <bitset>

#define DN 100005
using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");


bitset<DN> p;
int pr[80005],sz;
int fact[36];
long long N,P;

void gen()
{
    for(int i=2;i<DN;++i){

        if(!p[i]){

            for(int j=i+i;j<DN;j+=i)
                p[j]=1;

            pr[++sz]=i;
        }
    }
}
long long check(long long X)
{
    long long rez=X;
    for(int i=1;i<(1<<fact[0]);++i)
    {
        int nr=0;
        long long prod=1;
        for(int j=0;j<fact[0];++j)
            if( (1<<j) & i ){

                prod=prod*1ll*fact[j+1];
                ++nr;
            }
        if(nr%2) nr=-1;
            else
                nr=1;
        rez+=nr*1ll*X/prod;
        /// (-1) ^ (x-1)
    }
    return rez;
}

long long caut()
{
    long long rez=0,st=1,dr=(1ll<<61),mij;

    for(;st<=dr;){

            mij=(st+dr)/2;
            if( check(mij) >=P ){

                rez=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
    }
    return rez;
}

int main()
{
    gen();
    f>>N>>P;
    for(int t=1;N!=1;++t){

        int p=0;
        for(;N%pr[t]==0;++p,N/=pr[t]);
        if(p)
            fact[++fact[0]]=pr[t];
        if(pr[t]*pr[t]>N && N!=1)
            {
                fact[++fact[0]]=N;
                N=1;
            }
    }

    g<<caut();
    return 0;
}