#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

const int NMax = 1e6;

long long N, P, Sol, Ans, V[100], Div[100], NrDivs;
bool Prime[NMax + 5];
vector <long long> PrimesList;

void Sieve()
{
    for(int i = 2; i <= NMax; i++)
        if(Prime[i] == 0)
        {
            PrimesList.push_back(i);

            for(int j = 2 * i; j <= NMax; j += i)
                Prime[j] = 1;
        }
}

void Decompose()
{
    for(auto x : PrimesList)
    {
        if(x * x > N) break;
        if(N % x) continue;

        while(N % x == 0)
            N /= x;

        Div[++NrDivs] = x;
    }
    if(N > 1) Div[++NrDivs] = N;
}

void Back(long long Val, int pos, long long Prod)
{
    for(int i = V[pos - 1] + 1; i <= NrDivs; i++)
    {
        int s = ((pos % 2) ? 1 : -1);
        V[pos] = i; Sol += s * (Val / (Prod * Div[i]));

        if(pos < NrDivs)
            Back(Val, pos + 1, Prod * Div[i]);
    }
}

long long Number(long long Val)
{
    Sol = 0; Back(Val, 1, 1);
    return Val - Sol;
}

int main()
{
    fin >> N >> P;
    Sieve(), Decompose();

    for(long long step = (1LL << 60); step > 0; step >>= 1LL)
        if(Number(Ans + step) < P)
            Ans += step;

    fout << Ans + 1 << '\n';

    fin.close();
    fout.close();

    return 0;
}