#include <bits/stdc++.h>

using namespace std;

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

long long a, b, c;
vector<long long> d;

void divprim(long long x)
{
    d.clear();
    for (long long i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            d.push_back(i);
            while (x % i == 0)
            {
                x /= i;
            }
        }
    }
    if (x > 1)
    {
        d.push_back(x);
    }
}

void backtrack(int index, long long dc, int poz, long long urm)
{
    if (index > 0)
    {
        if (index % 2 == 0)
        {
            c = c - urm / dc;
        }
        else
        {
            c = c + urm / dc;
        }
    }
    for (int i = poz + 1; i < d.size(); i++)
    {
        dc = dc * d[i];
        backtrack(index + 1, dc, i, urm);
        dc /= d[i];
    }
}

int main()
{
    fin >> a >> b;
    divprim(a);

    long long left = 1, right = LLONG_MAX;
    while (left <= right)
    {
        long long mid = (left + right) / 2;
        c = 0;
        backtrack(0, 1, -1, mid);

        long long nr = mid - c;

        if (nr < b)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    fout << left;

    return 0;
}