#include<fstream>
#include<bitset>
#include<cstring>
#define INF 2305843009213693952

using namespace std;
ifstream fin("perm.in");
ofstream fout("perm.out");
long long v[1000001], i,j,sol,nr,n,k,st,mid,a;
long long dr;
bitset<1000001> u;

long long cauta(long long mid)
{
    long long k,x,j,sum=0;
    u.reset ();
    k=0;
    x=1;
    while(u[0]==0)
    {
        j=nr;
        while(u[j]==1)
        {
            k--;
            x/=v[j];
            u[j]=0;
            j--;
        }
        u[j]=1;
        k++;
        x*=v[j];
        if(j==0)
            break;
        if (k%2==1)
            sum+=mid/x;
        else
            sum-=mid/x;
    }
    return mid-sum;
}

long long cmmdc (long long a,long long b)
{
    long long r=0;
    while(b>0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int main()
{
    fin>>n>>k;
    nr=0;
    a=n;
    for(i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            v[++nr]=i;
            while(a%i==0)
                a/=i;
        }
    }
    if(a!=1)
        v[++nr]=a;
    st=1;
    dr=INF;
    while(st<=dr)
    {
        sol=0;
        mid=(st+dr)/2;
        if(mid!=0)
            sol=cauta(mid);
        if(sol==k)
        {
            if(cmmdc(mid, n)==1)
            {
                fout<<mid;
                break;
            }
            else
                dr=mid-1;
        }
        else
            if(sol>k)
                dr=mid-1;
            else
                st=mid+1;
    }
    fin.close();
    fout.close();
    return 0;
}