#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
using namespace std ;

#define maxv 5001

struct boss
{
    long long p, e ;
};

long long P, Q, nrv, sol ;

boss v[maxv] ;

void factorizare()
{
    for(long long x = 2; x * x <= P && P > 1; ++x )
    {
        long long exp  = 0 ;

        if( P % x == 0 )
        {
            while( P % x == 0 )
            {
                P /= x ;
                ++exp ;
            }

            ++nrv ;
            v[nrv].p = x ;
            v[nrv].e = exp * Q ;
        }
    }

    if( P > 1 )
    {
        ++nrv ;
        v[nrv].p = P ;
        v[nrv].e = Q ;
    }
}

long long exponent(long long p, long long n)
{
    long long ee = 0 ;

    while( n )
    {
        n /= p ;
        ee += n ;
    }

    return ee ;
}

long long cautbin(long long ind)
{
    long long st, dr, mij, ssol ;

    st = 1 ;
    dr = (long long)( 1LL << 59 ) ;
    ssol = 0 ;

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

        if( exponent( v[ind].p, mij ) >= v[ind].e )
        {
            ssol = mij ;
            dr = mij - 1 ;
        }
        else
            st = mij + 1 ;
    }

    return ssol ;
}

int main()
{
	std::ios_base::sync_with_stdio(false) ;

	freopen("gfact.in", "r", stdin);
	freopen("gfact.out", "w", stdout);

    cin >> P >> Q ;

    factorizare() ;

    for(long long i = 1 ; i <= nrv; ++i)
    {
        long long rez = cautbin(i) ;

        sol = max( sol, rez ) ;
    }

    cout << sol ;

	return 0 ;
}