#include<bits/stdc++.h>
using namespace std;

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

const int XMAX=400005;

int primes[XMAX];
long long n,p,st,mij,dr,sol,fact[30];
bitset<XMAX>viz;

void Ciur()
{
    int i;
    long long j;
    primes[++primes[0]]=2;
    for (i=3;i<XMAX;i+=2)
        if (!viz[i])
        {
            primes[++primes[0]]=i;
            for (j=1LL*i*i;j<XMAX;j+=i) viz[j]=1;
        }
}

void Back(int k,long long prod,int cnt)
{
    if (prod>mij) return ;
    if (k==fact[0]+1)
    {
        if (cnt==0) return;
        if (cnt&1) sol-=mij/prod;
        else sol+=mij/prod;
        return ;
    }
    Back(k+1,prod,cnt);
    Back(k+1,prod*fact[k],cnt+1);
}

int main()
{
    int i;
    long long aux,ans;
    fin>>n>>p;
    Ciur();
    //descomp
    aux=n;
    for (i=1;i<=primes[0] && 1LL*primes[i]*primes[i]<=aux;i++)
        if (aux%primes[i]==0)
        {
            fact[++fact[0]]=primes[i];
            while (aux%primes[i]==0) aux/=primes[i];
        }
    if (aux>1) fact[++fact[0]]=aux;

    st=1;dr=1LL<<60;
    while (st<=dr)
    {
        mij=(st+dr)>>1;
        sol=mij;
        Back(1,1,0);
        if (sol>=p)
        {
            ans=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }

    fout<<ans<<"\n";
    return 0;
}