#include <fstream>
#include <vector>

using namespace std;

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

const int rad_n = 110000;
long long n, p, log, sol;
vector < long long > P, D;
vector < bool > F(rad_n);

int main()
{
    fin >> n >> p;
    P.push_back(2);
    for (int i = 2; i <= rad_n; i += 2) F[i] = true;
    for (int i = 3; i <= rad_n; i += 2)
    {
        if (!F[i])
        {
            P.push_back(i);
            for (long long j = 1LL * i * i; j <= rad_n; j += i)
            {
                F[j] = true;
            }
        }
    }

    long long n_aux = n;
    for (int i = 0; i < P.size() && P[i] * P[i] <= n; i ++)
    {
        if (n % P[i] == 0)
        {
            while (n % P[i] == 0)
            {
                n /= P[i];
            }
            D.push_back(P[i]);
        }
    }
    if (n > 1) D.push_back(n);

    log = (1LL << 4);

    for (sol = log; log; log >>= 1)
    {
        long long nr = 0, nr_p = sol - log;
        if (sol - log > 0)
        {
            for (int i = 1; i < (1 << D.size()); i ++)
            {
                long long prod = 1, semn = 0;
                for (int j = 0; j < D.size(); j ++)
                {
                    if (i & (1 << j))
                    {
                        prod *= D[j];
                        semn ++;
                    }
                }

                if (semn & 1)
                {
                    nr += nr_p / prod;
                }
                else
                {
                    nr -= nr_p / prod;
                }
            }

            nr_p -= nr;
        }

        if (sol - log > 0 && nr_p >= p)
        {
            sol -= log;
        }
    }

    fout << sol << '\n';
    fout.close();
    return 0;
}