#include <fstream>
#include <vector>

using namespace std;

const long long VMAX = 1LL << 61;
///2 la 61 (e nevoie de LL pentru ca vrem ca 1 sa fie interpretat ca long long

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 nr_prime_cu(long long n, vector <long long> &dp)
{
    int ndp = (int)dp.size();
    long long nr = 0;
    for (int i = 0; i < (1 << ndp); i++)
    {
        int nrb1 = 0;
        long long div = 1;
        for (int j = 0; j < ndp; j++)
        {
            if (i & (1 << j))
            {
                nrb1++;
                div *= dp[j];
            }
        }
        if (nrb1 % 2 == 0)
        {
            nr += n / div;
        }
        else
        {
            nr -= n / div;
        }
    }
    return nr;
}

int main()
{
    ifstream in("frac.in");
    ofstream out("frac.out");
    long long n, p;
    in >> n >> p;
    vector <long long> dp;
    descompunere(n, dp);
    ///cautam binar cel mai mic rez cu propr, ca exista (cel putin) p numere prime cu n
    ///mai mici sau egale cu rez
    long long st = 1, dr = VMAX, rez = dr + 1;
    while (st <= dr)
    {
        long long m = (st + dr) / 2;
        if (nr_prime_cu(m, dp) >= p)
        {
            rez = m;
            dr = m - 1;
        }
        else
        {
            st = m + 1;
        }
    }
    out << rez << "\n";
    in.close();
    out.close();
    return 0;
}