#include <cmath>
#include <vector>
#include <bitset>
#include <climits>
#include <fstream>
#include <iostream>

using namespace std;

const int NMAX = 11e4 ;
bitset < NMAX + 5 > c ;
vector < int > primes ;

inline void ciur ( long long n )
{
    long long i , j , lim = ( long long ) sqrt ( ( double ) n ) ;

    c [ 0 ] = c [ 1 ] = 1 ;
    for ( i = 4 ; i <= n ; i += 2 )
        c [ i ] = 1 ;

    for ( i = 3 ; i <= lim ; i += 2 )
        if ( ! c [ i ] )
            for ( j = i * i ; j <= n ; j += i * 2 )
                c [ j ] = 1 ;

    primes.reserve ( 1e4 ) ;
    primes.push_back ( 2 ) ;
    for ( i = 3 ; i <= n ; i += 2 )
        if ( !  c [ i ] ) primes.push_back ( i ) ;
}

long long factors [ 25 ] , nr , med ;

inline void gen_fact ( long long x )
{
    long long d = 0 , ok ;
    nr = 0 ;

    while ( primes [ d ] * primes [ d ] <= x && d < primes.size () )
    {
        ok = 0 ;

        while ( x % primes [ d ] == 0 )
            x /= primes [ d ] , ok = 1 ;

        if ( ok ) factors [ ++ nr ] = primes [ d ] ;
        ++ d ;
    }

    if ( x != 1 ) factors [ ++ nr ] = x ;
}

inline long long numbers ( long long x )
{
    long long p , sign , i , j , cnt , ans = x ;

    for ( i = 1 ; i < ( 1 << nr ) ; ++ i )
    {
        sign = 1 ; p = 1 ; cnt = 0 ;

        for ( j = 0 ; j < nr ; ++ j )
            if ( ( 1 << j ) & i )
            {
                p *= factors [ j + 1 ] ;
                ++ cnt ;
            }

        if ( cnt % 2 ) sign = - 1 ;

        ans += sign * x / p ;
    }

    return ans ;
}

int main()
{
    ifstream in ( "frac.in" ) ;
    ofstream out ( "frac.out" ) ;

    long long n , p , st , dr , last , val ;
    ciur ( NMAX ) ;

    in >> n >> p ;
    gen_fact ( n ) ;

    st = 0 ; dr = LLONG_MAX ;

    while ( st <= dr )
    {
        med = ( st + dr ) >> 1 ;
        val = numbers ( med ) ;

        if ( val >= p )
            dr = med - 1 , last = med ;
        else
            st = med + 1 ;
    }

    out << last ;

    return 0;
}