#include <bits/stdc++.h>

using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
const int nmax=1100000;
long long b,k,st,dr,mij,rez,nr,nrc,prim[nmax],v[1001],s,p,i,j,K;
int ciur[nmax];
long long calc(long long a)
{
    int j;
    rez=0,nr=0,nrc=0,s=1;
    if(b>1)
        v[++k]=b;
            rez=a;
        for(j=1;j<(1LL<<k);j++)
        {
            nrc=0;
            s=1;
            for(p=0;p<k;p++)
            {
                if(((1LL<<p)&j)!=0)
                {
                    nrc++;
                    s=s*v[p+1];
                }
            }
            if(nrc%2==1)
            {
                rez=rez-a/s;
            }
            else
            {
                rez=rez+a/s;
            }
        }
    if(b>1)
        k--;
    return rez;
}
int main()
{
    for(i=2;i<=nmax;i++)
    {
        if(ciur[i]==0)
        {
            prim[++k]=i;
            for(j=i*2;j<=nmax;j+=i)
                ciur[j]=1;
        }
    }
    fin>>b>>K;
    k=0;
       for(j=1;1LL*prim[j]*prim[j]<=b;j++)
        {
            if(b%prim[j]==0)
            {
                v[++k]=prim[j];
                while(b%prim[j]==0)
                    b/=prim[j];
            }
        }
    st=1;
    dr=1;
    for(i=1;i<=30;i++)
        dr*=2;
    long long Max=LONG_LONG_MAX;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        nr=calc(mij);
        if(nr<K)
            st=mij+1;
        if(nr>=K)
        {
            dr=mij-1;
            if(nr==K)
                Max=min(Max,mij);
        }
    }
    fout<<Max;
    return 0;
}