#include <fstream>
#include <vector>

using namespace std;

const long long VMIN = 1;
const long long VMAX = 1LL << 61;

void descompunere(long long n, vector <long long> &dp)
{
    int d = 2;
    while ((long long)d * d <= n)
    {
        if (n % d == 0)
        {
            dp.push_back(d);
            while (n % d == 0)
            {
                n /= d;
            }
        }
        d++;
    }
    if (n != 1)
    {
        dp.push_back(n);
    }
}

long long prime_cu(vector <long long> &dp, long long x)
{
    int ndp = (int)dp.size();
    long long suma = 0;
    for (int m = 0; m < (1 << ndp); m++)
    {
        bool adun = true;
        long long prod = 1;
        for (int i = 0; i < ndp; i++)
        {
            if (m & (1 << i))
            {
                adun = (!adun);
                prod *= dp[i];
            }
        }
        if (adun)
        {
            suma += x / prod;
        }
        else
        {
            suma -= x / prod;
        }
    }
    return suma;
}

int main()
{
    ifstream in("frac.in");
    ofstream out("frac.out");
    long long n, p;
    in >> n >> p;
    vector <long long> dp;
    descompunere(n, dp);
    long long st = VMIN, dr = VMAX, rez = VMAX + 1;
    while (st <= dr)
    {
        long long m = (st + dr) / 2;
        if (prime_cu(dp, m) >= p)
        {
            rez = m;
            dr = m - 1;
        }
        else
        {
            st = m + 1;
        }
    }
    out << rez << "\n";
    in.close();
    out.close();
    return 0;
}