#include <fstream>
using namespace std;
ofstream fout ("frac.out");
ifstream fin ("frac.in");
long long n,p,aux,nrdiv,nrdivpin,nrprime,cs,cd,mij,suma,diviznr[110005],rsp;
bool eprim[110005];
long long prime[110005];
void ciur()
{
    eprim[ 1 ] = 1;
    for( int i = 2 ; i <= 110000 ; i++ )
    {
        if( eprim[ i ] == 0 )
        {
            prime[ ++nrprime ] = i;
            for( int j = i + i ; j <= 110000 ; j += i )
                eprim[ j ] = 1;
        }
    }
}
void divizorii( long long n )
{
    for( int i = 1 ; i <= nrprime ; i++ )
    {
        if( n % prime[ i ] == 0 )
        {
            diviznr[ ++nrdiv ] = prime[ i ];
            while( n % prime[ i ] == 0 )
                n /= prime[ i ];
        }
    }
    if( n != 1 )
        diviznr[ ++nrdiv ] = n;
}
long long pinex( long long nr )
{
    suma = 0;
    for( int i = 1 ; i < ( 1LL << nrdiv ) ; i++ )
    {
        rsp = 1;
        nrdivpin = 0;
        for( int j = 0 ; j < nrdiv ; j++ )
        {
            if( i & ( 1LL << j ) )
            {
                rsp *= diviznr[ j + 1 ];
                nrdivpin++;
            }
        }
        if( nrdivpin % 2 )
            suma += nr / rsp;
        else
            suma -= nr / rsp;
    }
    return nr - suma;
}
int main()
{
    fin>>n>>p;
    ciur();
    divizorii( n );
    cs = 1;
    cd = ( 1LL << 61 );
    while( cs <= cd )
    {
        mij = ( cs + cd ) / 2;
        if( pinex( mij ) >= p )
        {
            rsp = mij;
            cd = mij - 1;
        }
        else
            cs = mij + 1;
    }
    fout<<rsp;
}