#include <fstream>
#include <vector>
#define ll long long
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
ll n,p,l;
ll v[1005];
void divizori(ll x)
{
    ll k=2;
    while(k*k<=x)
    {
        if(x%k==0)
        {
            while(x%k==0)
                x/=k;
            v[++l]=k;
        }
        ++k;
    }
    if(x>1)
        v[++l]=x;
}
ll pinex(ll a)
{
    ll maxim = (1<<l)-1, rez = 0;
    for(ll i=1; i<=maxim; ++i)
    {
        ll nr = 0, prod = 1;
        for(int j=0; j<l; ++j)
            if(i&(1LL<<j))
            {
                prod*=v[j];
                ++nr;
            }
        if(nr%2==1)
            rez+=a/prod;
        else
            rez-=a/prod;
    }
    return rez;
}
int main()
{
    f>>n>>p;
    divizori(n);
    ll st = 1, dr = (1LL<<61), last = 1;
    while(st<=dr)
    {
        ll mijl = (st+(dr-st)/2);
        ll aux = pinex(mijl);
        if(mijl - aux >= p)
        {
            last = mijl;
            dr = mijl-1;
        }
        else st = mijl+1;
    }
    g << last;
    return 0;
}