#include <bits/stdc++.h>

using namespace std;

ifstream fin("frac.in");

ofstream fout("frac.out");

vector<int> divizori;

bool da[100];

long long int rez(long long int a)
{
    long long int rez1 = a;

    for (long long int i = 0; i < divizori.size(); i++)
        da[i] = 0;
    while (!da[0])
    {
        long long i = divizori.size() - 1;
        while (da[i])
        {
            da[i] = false;
            i--;
        }
        da[i] = true;
        long long int sclav = 1;
        int cnt = 0;
        for (int k = 0; k < divizori.size(); k++)
        {
            if (da[k])
            {
                sclav *= divizori[k];
                cnt++;
            }
        }
        if (sclav != 1)
        {
            if (cnt % 2)
                rez1 -= a / sclav;
            else
                rez1 += a / sclav;
        }
    }
    return rez1;
}
int n, p;
int main()
{
    fin >> n >> p;
    int sclav = n;
    for (int i = 2; sclav != 1 && i * i <= sclav; i++)
    {
        if (sclav % i == 0)
            divizori.push_back(i);
        while (sclav % i == 0)
        {
            sclav /= i;
        }
    }
    if (sclav != 1)
        divizori.push_back(sclav);
    long long int st = 1;
    long long int dr = (1LL << 61);
    while (st <= dr)
    {
        long long int mij = (st + dr) / 2;
        long long int k = rez(mij);
        if (k < p)
        {
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    fout << st;
}