#include <iostream>
#include <fstream>

using namespace std;

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

int v[11];
int k, k2;
//char ciur[1000001];


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

long long pr( int n, int j )
{
    int i, l;
    long long sum = 0;
    for ( i = 1; i < k2; i ++ )
    {
        int prod = 1;
        int ci = i;
        int 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, suma, rez;
    int i, j;
    f >> n >> p;
    divizori_primi(n);
    long long st = 1, dr = LONG_MAX;
    k2 = (1 << k);
    pr( n, 8 );
    while ( st <= dr)
    {
        int mij = (st + dr) / 2;
        if ( pr( n, mij ) >= p)
        {
            rez = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    g << rez;
    return 0;
}