#include <bits/stdc++.h>
using namespace std;
vector <long long> v;
long long prime( long long a ){
    long long i, j, l, p, nr, x, r;
    l = pow( 2, v.size() );
    r = 0;
    for( i = 1; i < l; i++ ){
        x = i;
        p = 1;
        nr = 0;
        for( j = 0; j < v.size(); j++ ){
            if( x % 2 == 1 ){
                p *= v[j];
                nr++;
            }
            x /= 2;
        }
        ///cout << a << ' ' << i << ' ' << p << '\n';
        if( nr % 2 == 1 ){
            r += a / p;
        }
        else{
            r -= a / p;
        }
    }
    ///cout << a << ' ' << a - r << '\n';
    return a - r;
}
int main(){
    long long n, p, stanga, dreapta, mijloc, d;
    ifstream fin( "frac.in" );
    ofstream fout( "frac.out" );
    fin >> n >> p;
    d = 2;
    while( d * d <= n ){
        if( n % d == 0 ){
            v.push_back( d );
            while( n % d == 0 ){
                n /= d;
            }
        }
        d++;
    }
    if( n > 1 ){
        v.push_back( n );
    }
    /**for( int i = 0; i < v.size(); i++ ){
        cout << v[i] << ' ';
    }
    cout << '\n';*/
    stanga = 0;
    dreapta = pow( 2, 61 );
    while( dreapta - stanga > 1 ){
        mijloc = ( stanga + dreapta ) / 2;
        ///cout << stanga << ' ' << dreapta << ' ' << mijloc << ' ' << prime( mijloc ) << ' ' << p << '\n';
        if( prime( mijloc ) < p ){
            stanga = mijloc;
        }
        else{
            dreapta = mijloc;
        }
    }
    fout << dreapta;
    return 0;
}