#include <bits/stdc++.h>
using namespace std;
#define ll long long
#if 1
#define cin fin
#define cout fout
ifstream fin("frac.in");
ofstream fout("frac.out");
#endif // 0
const ll nmx = 1e6;
ll era[nmx];
vector<ll> pr;
void calcEras(){
    era[0] = era[1] = 1;
    for(ll i=4;i<nmx;i+=2)
        era[i] = 1;
    for(ll i=3;i<nmx;i+=2)
        if(era[i] == 0)
            for(ll j=i*i;j<nmx;j+=i)
                era[j] = 1;

    for(ll i=0;i<nmx;i++)
        if(era[i] == 0)
            pr.push_back(i);
}

vector<ll> dec(ll x){
    vector<ll> v;
    ll i = 0;
    while(pr[i]*pr[i]<=x){
        if(x%pr[i]==0){
            v.push_back(pr[i]);
            do
                x /= pr[i];
            while(x%pr[i]==0);
        }
        i++;
    }
    if(x!=1)
        v.push_back(x);
    return v;
}

ll n;
ll eval(ll k){ /// returns the number of numbers smaller than k that are prime with n
    auto dvs = dec(n);
    ll ans = 0;
    for(ll msk=1;msk<(1<<dvs.size());msk++){
        ll cnt = 0, nr = 1;
        for(ll j=0;j<dvs.size();j++)
            if(msk&(1<<j))
                cnt++, nr*=dvs[j];
        ans += (cnt&1?1:-1)*k/nr;
    }
    return k-ans;
}

int main()
{
    calcEras();
    ll p;
    cin >> n >> p;
    ll st = 0, dr = (1LL<<61);
    ll ans = 0;
    while(st<=dr){
        ll md = (st + dr)/2;
        ll val = eval(md);
        if(val >= p){
            ans = md;
            dr = md-1;
        }
        else
            st = md+1;
    }
    cout << ans;
}