#include <bits/stdc++.h>

using namespace std;

const long long VAL_MAX = 12e9 + 5;
int NrP;

vector<int> primes;

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void FindPrimeFactors(int x)
{
    for(long long i = 2; i < VAL_MAX && i * i <= x; i++)
        if(x % i == 0)
        {
            primes.push_back(i);
            while(x % i == 0)
                x /= i;
        }

    if(x != 1)
        primes.push_back(x);

    NrP = primes.size();
}

long long orderOf(long long n)
{
    long long p = n;
    long long MASK_MAX = (1 << NrP) - 1;

    for(int mask = 1; mask <= MASK_MAX; mask++)
    {
        long long prod = 1, cnt = 0;

        for(int i = 0; i < NrP; i++)
            if((mask & (1 << i)) != 0)
            {
                prod *= primes[i];
                cnt++;
            }

        long long val = n / prod;

        if(cnt % 2 == 1)
            p -= val;
        else
            p += val;
    }

    return p;
}

void Solve()
{
    long long N, P, sol = 0;

    cin >> N >> P;

    FindPrimeFactors(N);

    long long st = 1, dr = VAL_MAX;

    while(st <= dr)
    {
        int m = (st + dr) / 2;

        if(orderOf(m) >= P)
        {
            sol = m;
            dr = m - 1;
        }
        else
            st = m + 1;
    }

    cout << sol << '\n';
}

int main()
{
    SetInput("frac");

    Solve();

    return 0;
}