#include <fstream>
#include <vector>
#define int long long

using namespace std;

ifstream cin("frac.in");
ofstream cout("frac.out");

const int NMAX = 1e6;

int N, P, ans;

vector<int> prime;
bool eprim[NMAX+1];
vector<int> factoriprimi;


void eratostene()
{
    for(int i = 3; i <= NMAX; i+= 2)
    {
        if(eprim[i] == 0)
            for(int j = i + i; j <= NMAX; j += i)
                eprim[j] = 1;
    }

    prime.push_back(2);
    for(int i = 3; i <= NMAX; i++)
    {
        if(eprim[i] == 0 && i % 2)
            prime.push_back(i);
    }
}

void Desc(int B)
{
    int ind = 0, d = prime[0];
    while(B != 1)
    {
        if(B % d == 0)
        {
            factoriprimi.push_back(d);
            while(B % d == 0)
                B /= d;
        }
        if(prime[ind+1] * prime[ind+1] > B)
            d = B;
        else d = prime[++ind];
    }
}

void rez(vector<int> sub, int n, int valoare)
{
    int prod = 1LL;
    for(int i = 1LL; i <= n; i++)
        prod *=1LL * factoriprimi[sub[i]];
    if(n % 2)
        ans += valoare / prod;
    else ans -= valoare / prod;
}

void Back(vector<int> &sub, int k, int val)
{
   for(int i = sub[k-1] + 1LL; i < factoriprimi.size(); i++)
   {
       sub[k] = i;
       rez(sub, k, val);
       if(k < factoriprimi.size())
            Back(sub, k+1LL, val);
   }
}

int catiprimi(int x)
{
    vector<int> submultimi(factoriprimi.size() + 1);
    submultimi[0] = -1LL;
    Back(submultimi, 1LL, x);
    return x - ans;
}

signed main()
{
    eratostene();
    cin >> N >> P;

    Desc(N);

    int st = 1, dr = (1LL << 61), res = -1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        ans = 0;
        if(catiprimi(mij) >= P)
        {
            res = mij;
            dr = mij - 1LL;
        }
        else
        {
            st = mij + 1LL;
        }
    }

    cout << res;
}