#include <fstream>
#include <vector>
using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

using LL = unsigned long long;
LL N, P;
vector<LL> D;  /// divizorii primi ai lui N
vector<LL> v;
LL rez;
LL nre, l;

void Read();
void DescompuneN();
void Binary_Search();
LL NrIreductibile( LL m );
void Back( LL h, vector<LL>::iterator it );

int main()
{
    Read();
    DescompuneN();
    Binary_Search();

    fout << rez;

    fin.close();
    fout.close();
    return 0;
}


void Read()
{
    fin >> N >> P;
}

void DescompuneN()
{
    LL d;

    if ( N % 2 == 0 )
    {
        D.push_back(2);
        while ( N % 2 == 0 )
            N /= 2;
    }

    for ( d = 3; d * d <= N; d += 2 )
        if ( N % d == 0 )
        {
            D.push_back(d);
            while ( N % d == 0 )
                N /= d;
        }

    if ( N > 1 )
        D.push_back(N);
}

void Binary_Search()
{
    LL st = 1, dr = (1LL<<61LL), mij, ir;

    while ( st <= dr )
    {
        mij = ( st + dr ) / 2;
        ir = NrIreductibile(mij);

        if ( ir >= P )
        {
            rez = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
}

LL NrIreductibile( LL m )
{
    nre = 0; l = m;
    Back(1, D.begin());

    return l - nre;
}

void Back( LL h, vector<LL>::iterator it )
{
    if ( h > 1 )
    {
        LL nr = 1;
        for ( const auto& x : v )
            nr *= x;

        if ( ( h - 1 ) % 2 == 1 )
            nre = ( nre + ( l / nr ) );
        else
            nre = ( nre - ( l / nr ) );
    }

    for ( ; it != D.end(); ++it )
    {
        v.push_back(*it);
        Back(h + 1, it + 1);
        v.pop_back();
    }
}