#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

FILE *f = fopen ( "frac.in", "r" );
FILE *g = fopen ( "frac.out", "w" );

vector < int > Divs;

long long Pinex ( long long x ){

    int NrBits, sgn = 1, go = (1 << Divs.size());
    long long rez = 0, prod;

    for ( int i = 0; i < go; ++i ){
        prod = 1;
        NrBits = 0;
        sgn = 1;
        for ( int j = 1, k = 0; j <= i; j <<= 1, ++k ){
            if ( i & j ){
                NrBits++;
                prod *= Divs[k];
            }
        }
        if ( NrBits & 1 )
            sgn = -1;

        rez += sgn * x / prod;
    }

    return rez;
}

int main(){

    long long N, P;
    vector < int > :: iterator it;

    fscanf ( f , "%lld%lld", &N, &P );

    for ( int i = 2; i * i <= N; ++i ){
        if ( N % i == 0 ){
            Divs.push_back(i);
            while ( N % i == 0 )
                N /= i;
        }
    }
    if ( N != 1 )
        Divs.push_back(N);

    long long sol, st = 1, dr = ( 1LL << 61 );

    while ( st <= dr ){
        long long mid = ( st + dr ) >> 1;

        if ( Pinex(mid) >= P ){
            sol = mid;
            dr = mid - 1;
        }
        else
            st = mid + 1;
    }

    fprintf ( g, "%lld", sol );

    return 0;
}