#include <fstream>

using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long n,p,st[100],q,s,m,nr,a[100],k;
bool v[100];
void calc()
{
    int i;
    q=1;
    for(i=1; i<=k; i++)q*=a[st[i]];
    if(k%2==1)s-=m/q;
    else s+=m/q;
}
void back(int top)
{
    int i;
    if(top==k+1)calc();
    else for(i=st[top-1]+1; i<=nr; i++)
        {
            if(v[i]==0)
            {
                st[top]=i;
                v[i]=1;
                back(top+1);
                v[i]=0;
            }
        }
}
int main()
{
    long long i,dr,st,ok;
    fin>>n>>p;
    m=n;
    for(i=2; i<=n; i++)
    {
        if(n%i==0)
        {
            nr++;
            a[nr]=i;
            while(n%i==0)n/=i;
        }
    }
    st=1;
    dr=10000000000000000;
    while(st!=dr)
    {
        m=(st+dr)/2;
        s=m;
        for(i=1; i<=nr; i++)
        {
            k=i;
            back(1);
        }
        if(s>=p)dr=m;
        else st=m+1;
    }
    while(!ok)
    {
        ok=1;
        for(i=1; i<=nr; i++)
            if(st%a[i]==0)
            {
                st++;
                ok=0;
                break;
            }
    }
    fout<<st;
}