#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

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

ll n, p, s, st = 1, dr = (1LL << 61), mij;
int x[20];
bool ok = 1;
vector<ll> divi;

void descomp(ll x)
{
    if(x % 2 == 0)
    {
        divi.push_back(2);
        do
        {
            x /= 2;
        }
        while(x % 2 == 0);
    }
    for(ll d = 3; d * d <= x; d += 2)
        if(x % d == 0)
        {
            divi.push_back(d);
            do
            {
                x /= d;
            }
            while(x % d == 0);
        }
    if(x > 1) divi.push_back(x);
}

void bt(int k, ll prod)
{
    for(unsigned int i = x[k - 1] + 1; i < divi.size(); ++i)
    {
        x[k] = i;
        ll t = prod * divi[i];
        if(k & 1) s -= mij / t;
        else s += mij / t;
        bt(k + 1, t);
    }
}

int main()
{
    fin >> n >> p;
    descomp(n);
    x[0] = -1; //(*)
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        s = mij;
        bt(1, 1LL);
        if(s > p) dr = mij - 1;
        else if(s < p) st = mij + 1;
        else break;
    }
    while(ok)
    {
        ok = 0;
        for(const auto& x : divi)
            if(mij % x == 0)
            {
                ok = 1, --mij;
                break;
            }
    }
    fout << mij;
    return 0;
}