#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");

typedef long long ll;

int d;
ll a[20];

ll f(ll nr)
{
    int i;
    ll s = nr;
    for(i = 1 ; i < (1 << d) ; i++)
    {
        ll x = 1;
        int ci = i;
        int l = 1;
        int t = 0;
        while(ci)
        {
            if(ci % 2 == 1)
            {
                x *= a[l];
                t++;
            }
            ci /= 2;
            l++;
        }
        if(t % 2 == 0)
        {
            s += nr / x;
        }
        else
        {
            s -= nr / x;
        }
    }
    return s;
}

int main()
{
    ll n, p, st, dr, ok;
    fin >> n >> p;
    st = 1;
    dr = (1LL<<61);
    d = 0;
    for(int i = 2 ; i * i <= n ; i++)
    {
        if(n % i == 0)
        {
            a[++d] = i;
            while(n % i == 0)
                n /= i;
        }
    }
    if(n != 1)
        a[++d] = n;
    while(st <= dr)
    {
        ll mij = (st + dr) >> 1;
        if(f(mij) >= p)
        {
            ok = mij;
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    fout << ok << "\n";
}