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

ifstream is("gfact.in");
ofstream os("gfact.out");

#define ll long long

vector<pair<ll,ll> > Factor;

ll P, Q;
void FactorizeP();
void BinarySearch();
bool Check(ll x);

int main()
{
    is >> P >> Q;

    FactorizeP();
    BinarySearch();


    is.close();
    os.close();
    return 0;
}

void FactorizeP()
{
    ll base, exp;
    ll aux = P;
    for ( ll i = 2; i * i <= P; ++i )
    {
        if ( P % i == 0 )
        {
            base = i;
            exp = 0;
            while ( P % i == 0 )
                exp++,P/=i;
            Factor.push_back(make_pair(base,exp));
        }
    }
    if ( P > 1)
        Factor.push_back(make_pair(P,1));
}

void BinarySearch()
{
    ll i(0), Step(1);
    for ( int i = 1;i <= 61; ++i)
        Step *= 2;

    for ( ; Step; Step /= 2)
        if ( Check(i+Step) == false )
           i += Step;
    os << i+1;
}

bool Check(ll x)
{
    ll aux2;
    ll aux3;
    for ( ll i = 0; i < Factor.size() ; ++i )
    {
        aux2 = Factor[i].first;
        aux3 = 0;
        while ( x >= aux2 )
        {
            aux3 += x/aux2;
            aux2 *= Factor[i].first;
        }
        if ( aux3 < Factor[i].second * Q )
            return false;
    }
    return true;
}