#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define dim 200005
using namespace std;
bitset<dim>ciur;
vector<int>primes;
void sieve()
{
    ciur[0] = ciur[1] = 1;
    for(int i = 4; i <= dim; i += 2)
    {
        ciur[i] = 1;
    }
    for(int i = 3; i * i <= dim; i += 2)
    {
        if(!ciur[i])
        {
            for(int j = i * i; j <= dim; j += 2 * i)
            {
                ciur[j] = 1;
            }
        }
    }
    primes.push_back(2);
    for(int i = 3; i <= dim; i += 2)
    {
        if(!ciur[i])
        {
            primes.push_back(i);
        }
    }
}
ll n, a, st, dr, mid, sol, p;
ifstream fin("frac.in");
ofstream fout("frac.out");
int32_t main(int argc, char * argv[])
{
    sieve();
    fin >> n >> p;
    ll aux = n;
    vector<int>divisors;
    int k = 0;
    while(k < primes.size() && primes[k] * primes[k] <= n)
    {
        if(n % primes[k] == 0)
        {
            divisors.push_back(primes[k]);
            while(n % primes[k] == 0)
            {
                n /= primes[k];
            }
        }
        k++;
    }
    if(n > 1)
    {
        divisors.push_back(n);
        n = 1;
    }
    int val = p;
    st = 1, dr = 1ll * 12e9;
    while(st <= dr)
    {
        mid = 1ll * (st + dr) / 2; // cate numere mai mici sau  egale  ca mid sunt prime cu n(ar trebui sa dea p )
        ll semn = 1, nrdiv = divisors.size(), card = 1, solution = 0, nrsub = 0;
        for(int i = 1; i < (1 << nrdiv); ++i)
        {
            semn = 1, card = 1, nrsub = 0;
            for(int j = 0; j < nrdiv; ++j)
            {
                if(i & (1 << j))
                {
                    nrsub++;
                    card *= divisors[j];
                }
            }
            if(nrsub % 2)
            {
                semn = 1;
            }
            else
            {
                semn = -1;
            }
            solution += 1ll * semn * mid / card;
        }
        if(mid - solution == val)
        {
            sol = mid;
            dr = mid - 1;
        }
        else
        {
            if(mid - solution < val)
            {
                st = mid + 1;
            }
            if(mid - solution > val)
            {
                dr = mid - 1;
            }
        }

    }
    fout << sol;
    return 0;
}