#include <bits/stdc++.h>

using namespace std;

const long long VAL_MAX = 1LL << 61;
int NrP;

vector<long long> primes;
vector<pair<long long, bool>> factors; /// (value, event cnt)

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();
}

void PrecalcFactors()
{
    long long MASK_MAX = (1LL << NrP) - 1;

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

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

        if(cnt % 2 == 0)
            factors.emplace_back(prod, true);
        else
            factors.emplace_back(prod, false);
    }
}

long long orderOf(long long n)
{
    long long p = n;

    for(const pair<long long, bool>& prod : factors)
        if(prod.second)
            p += n / prod.first;
        else
            p -= n / prod.first;

    return p;
}

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

    cin >> N >> P;

    FindPrimeFactors(N);
    PrecalcFactors();

    long long st = 1, dr = VAL_MAX;

    while(st <= dr)
    {
        long long 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;
}