#include <bits/stdc++.h>

using namespace std;

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

//#define int long long

long long n,p,N;
vector<long long>f;
bool iau[20];
long long sum;
long long nrr;

void afis()
{
    long long pr = 1,tip = -1;
    for (long long i = 0; i < f.size(); i++)
    {
        if (iau[i] == true)
        {
            tip = -tip;
            pr *= f[i];
        }
    }
    if (pr != 1)
        sum += (tip * (nrr / pr));
}

void bkt(int pos)
{
    if (pos == f.size())
        afis();
    else
    {
        iau[pos] = false;
        bkt(pos + 1);
        iau[pos] = true;
        bkt(pos + 1);
    }
}

long long cate(long long x)
{
    nrr = x;
    sum = 0;
    bkt(0);
    //out << x << ' ' << sum << '\n';
    return x - sum;
}

int main()
{
    in >> n >> p;
    N = n;
    for (long long i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            f.push_back(i);
            while (n % i == 0)
                n /= i;
        }
    }
    if (n != 1)
        f.push_back(n);
    long long st = 0,pas = 1ll << 60;
    while (pas != 0)
    {
        if (cate(st + pas) < p)
            st += pas;
        pas /= 2ll;
    }
    st++;
    out << st;
    return 0;
}