#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin ("frac.in");
ofstream fout ("frac.out");
ll n, p;
vector<ll> v;
void divizori(ll x)
{
    ll k = 2;
    while(k*k<=x)
    {
        if(x%k == 0)
        {
            while(x%k==0)
                x/=k;
            v.push_back(k);
        }
        ++k;
    }
    if(x > 1)
        v.push_back(x);
}
ll pinex(ll a)
{
    ll maxim = (1<<v.size())-1, rez = 0;
    for(ll i=1; i<=maxim; ++i)
    {
        ll nr = 0, prod = 1;
        for(int j=0; j<v.size(); ++j)
            if(i&(1LL<<j))
            {
                prod*=v[j];
                ++nr;
            }
        if(nr%2==1)
            rez+=a/prod;
        else
            rez-=a/prod;
    }
    return rez;
}
ll cmmdc(ll a, ll b)
{
    if(b > a)
        swap(a, b);
    ll r = 0;
    while(r)
    {
        a = b;
        b = r;
        r = a%b;
    }
    return b;
}
int main()
{
    fin >> 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;
    }
    fout << last;
    return 0;
}