#include <fstream>
#include <cmath>
using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");

long long  n;
long long  fact[1000],poz;
long long  sol=0;
int calc(long long  b)
{
   long long  d=2;
    while(b>1)
    {
        bool g=0;
        while(b%d==0)
        {
            g=1;
            b/=d;
        }
        if(g)
        {
            poz++;
            fact[poz]=d;
        }
        if(d==2)
        {
            d++;
        }
        else
        {
            d+=2;
        }


    }





}
long long  calc1(long long  a,long long  b)
{
       sol=0;
    long long  cnt=0,prod;
    for(int i=1;i<(1<<poz);i++)
    {
        cnt=0;
        prod=1;

        for(int k=0;k<poz;k++)
        {
            if((1<<k) & i)
            {
                prod*=fact[k+1];
                cnt++;
            }
        }
        if(cnt%2==0)
        {
            cnt=-1;
        }
        else
        {
            cnt=1;
        }
        sol+=(a/prod)*cnt;
    }
    return a-sol;
}



int main()
{

   long long  a,b;
        cin>>a>>b;
       long long st=1,dr=100000000,mij,pozf;
        calc(a);

            while(st<=dr)
            {
                mij=(dr+st)/2;
                calc1(mij,a);
                if(mij-sol==b)
                {
                    pozf=mij;
                    break;
                }
                else if(mij-sol>b)
                {
                    dr=mij-1;
                }
                else
                {
                    st=mij;
                }

            }

        while(1)
        {
            if(calc1(pozf,a)==calc1(pozf-1,a))
            {
                pozf--;
            }
            else
            {
                break;
            }
        }
        cout<<pozf;







    return 0;
}