/*
    Keep It Simple!
*/

#include <fstream>
#include <iostream>
#include <cmath>

#define Upper_Bound 1000000
#define ll long long

using namespace std;

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

const int Max_PrimeC = 90000;
const ll Max_N = 12000000005;

ll T,A,B,P,factors[30];
int p_count,primes[Max_PrimeC],f_count;
bool seen[Upper_Bound];

void GeneratePrimes()
{
    primes[++p_count] = 2;
    for(int i=3; i <= Upper_Bound; i+=2)
    {
        if(!seen[i])
        {
            primes[++p_count] = i;
            for(int j=i+i; j <= Upper_Bound; j+=i)
                seen[j] = 1;
        }
    }
}

void ComputeFactors(ll B)
{
    int idx = 1;
    while(B!=1)
    {
        if(!(B%primes[idx])) factors[++f_count] = primes[idx];
        while(!(B%primes[idx])) B/=primes[idx];
        idx++;

        if(primes[idx] > sqrt(B) && B > 1)
        {
            factors[++f_count] = B;
            B = 1;
        }
    }
}

ll pinex(ll A,ll B)
{
    ll solution = A;

    for(int i=1; i < (1 << f_count); ++i)
    {
        int sign = 0;
        ll prod = 1;
        for(int j=0; j < f_count; j++)
            if( (1<<j) & i)
            {
                prod = 1LL * factors[j+1] * prod;
                sign ++;
            }

        if(sign%2) sign = -1;
        else sign = 1;

        solution = solution + 1LL * sign * A / prod;
    }
    return solution;
}

bool IsPrime(ll x)
{
    if(x < Upper_Bound)
        return !seen[x];
    else
    {
        for(int i=1; i<=p_count; ++i)
            if(x%primes[i]==0)
                return 0;
    }
    return 1;
}

ll FirstPrimeDown(ll left,ll right)
{
    for(ll i=right; i >= left; i--)
        if(IsPrime(i))
            return i;
    return -1;
}

void Solve()
{
    fin >> B >> P;
    GeneratePrimes();

    f_count = 0;
    ComputeFactors(B);

    //Binary Search for solution
    ll left = 0, right = Max_N;
    int lower_bound_count = 0;
    int ok = 0;

    while( left < right && !ok)
    {
        ll middle = (left + right) / 2;
        ll prime_count = pinex(middle,B);

        if(prime_count > P)
        {
            right = middle-1;
        }
        else if(prime_count == P)
        {
            // go from right downwards till first prime
            right = middle;
            ok = 1;
        }
        else if(prime_count < P)
        {
            left = middle;
        }
    }

        fout << FirstPrimeDown(left,right);

}

int main()
{
    Solve();
    return 0;
}