#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long d,n,t,p,i,j,k,prime[20000],diviz[100],g[100],st,dr,rez,mid,total,aux,nrdiv;
bitset <200000> b;
int main(){
    fin>>n>>p;
    for(i=2;i<200000;i++)
        if(b[i]==0){
            prime[++k]=i;
            for(j=i+i;j<200000;j+=i)
                b[j]=1;
        }
    for(d=1;n!=1 && prime[d]<=n/prime[d] && d<=k;d++)
        if(n%prime[d]==0){
            diviz[++t]=prime[d];
            while(n%prime[d]==0)
                n/=prime[d];
        }
    if(n>1)diviz[++t]=n;
    st=1;
    dr=(1LL<<61);
    while(st<=dr){
        mid=(st+dr)/2;
        g[0]=total=0;
        while(!g[0]){
            for(i=t;g[i];i--)
                g[i]=0;
            g[i]=1;
            if(i==0)break;
            aux=1;
            nrdiv=0;
            for(;i;i--)
                if(g[i]){
                    nrdiv++;
                    aux*=diviz[i];
                }
            if(nrdiv%2)
                total+=mid/aux;
            else total-=mid/aux;
        }
        rez=mid-total;
        if(rez<p)
            st=mid+1;
        else dr=mid-1;
    }
    fout<<st;
    return 0;
}