#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

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

long long v[11];
long long k, k2;

void divizori_primi( long long n )
{
    long long i;
    long long cn = n;
    for ( i = 2; i*i <= n; i ++ )
    {
        if ( n % i == 0)
        {
            v[++k] = i;
            while( n % i == 0 )
                n /= i;
        }
    }
    if ( n > 1 )
        v[++k] = n;
}

long long pr( long long n, long long j )
{
    long long i, l;
    long long sum = 0;
    for ( i = 1; i < k2; i ++ )
    {
        long long prod = 1;
        long long ci = i;
        long long paritate = 0;
        for ( l = 1; l <= k; l ++ )
        {
            if ( ci % 2 == 1 )
            {
                paritate ++;
                prod *= v[l];
            }
            ci /= 2;
        }
        if( paritate % 2 == 1)
            sum += j/prod;
        else sum -= j/prod;
    }
    return j - sum;
}

int main()
{
    long long n, p, rez = -1;
    f >> n >> p;
    divizori_primi(n);
    long long st = 1, dr = 99999999999999;
    k2 = (1 << k);
    while ( st <= dr)
    {
        long long mij = (st + dr) / 2;
        if ( pr( n, mij ) >= p)
        {
            rez = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    //cout << k;
    g << rez;
    return 0;
}