#include <fstream>
#include <cmath>
#include <bitset>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
bitset <110000> viz;
long long n,p,m,st,dr,nr,best;
int i,c,a[25],l,o,j,v[15001],ve[25];
void bt(int i)
{
    long long j,l,u;
    if (i==o+1)
    {
        u=0;
        l=m;
        for (j=1;j<=o;j++)
            if (a[j]==1) u++,l=l/ve[j];
            if (u)
            {
            if (u%2==0) nr-=l;
            else nr+=l;
            }
    }
    else for (j=0;j<=1;j++)
        a[i]=j,bt(i+1);
}
int main()
{
    f>>n>>p;
    c=sqrt(n);
    viz[1]=true;
    l=1;
    v[1]=2;
    for (i=3;i<=c;i+=2)
     if (viz[i]==false)
        {
            j=i*i;
            if (j/i==i)
                for (j=i*i;j<=c;j+=i)
                viz[j]=true;
           v[++l]=i;
        }
 
    o=0;
    for (j=1;j<=l;j++)
        if (n%v[j]==0) ve[++o]=v[j];
    st=1,dr=1ll<<61-2;
    while(st<=dr)
    {
        m=(st+dr)>>1;
        nr=0;
        bt(1);
        if (m-nr>=p) best=m,dr=m-1;
        else st=m+1;
    }
    g<<best;
    return 0;
}