#include <bits/stdc++.h>

#define ll long long
#define sqrtB 1000005

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

ll N, P;
bool c[sqrtB];
vector <int> primes;
vector <ll> d;

vector <ll> getPrimeDiv(ll B)
{
    vector <ll> ret;
    for(auto it : primes)
        if(B % it == 0)
        {
            ret.push_back(it);
            while(B % it == 0)
                B /= it;
        }
    if(B != 1)
        ret.push_back(B);
    return ret;
}

ll solve(ll A, ll B)
{
    ll ret = A;
    for(int i = 1; i < (1 << d.size()); i++)
    {
        int cnt = 0;
        ll prod = 1;
        for(int j = 0; (1 << j) <= i; j++)
            if(i & (1 << j))
                prod *= d[j], cnt++;
        if(cnt % 2 == 1)
            ret -= A / prod;
        else
            ret += A / prod;
    }
    return ret;
}

int main()
{
    for(int i = 2; i <= 1000000; i++)
        c[i] = true;
    c[1] = false;
    for(int i = 2; i <= 1000; i++)
        if(c[i])
            for(int j = i * i; j <= 1000000; j += i)
                c[j] = false;
    for(int i = 2; i <= 1000000; i++)
        if(c[i])
            primes.push_back(i);
    fin >> N >> P;
    ll le = 0, ri = 1ll << 61, mid, best;
    d = getPrimeDiv(N);
    while(le <= ri)
    {
        mid = le + (ri - le) / 2;
        if(solve(mid, N) >= P)
        {
            ri = mid - 1;
            best = mid;
        }
        else
            le = mid + 1;
    }
    fout << best << "\n";
    return 0;
}