# include <cstdio>

typedef long long ll ;
const char FIN[] = "gfact.in", FOU[] = "gfact.out" ;

int P, Q ;
int sol ;

void nothing ( ) { } ;

ll check ( ll P, ll Q )
{
    ll rez ;
    for ( rez = 0 ; P ; P /= Q , rez += P ) ;
    return rez ;
}

void search ( ll P, ll Q )
{
    ll i, cnt = ( ll ) 1 << 50 ;

    for (i = 0; cnt ; cnt >>= 1 )
        if ( check ( i + cnt, P ) < Q )
            i += cnt ;

    if ( sol - 1 < i ) sol = i ;
}

void solve ()
{
    for (int i = 2; i * i <= P; ++i)
        if ( P % i == 0 )
            for ( int X = 0 ; P % i == 0 ; P /= i, X += Q, P % i ? search ( i , X ) : nothing () ) ;

    if ( P != 1 ) search ( P , Q ) ;
}

int main()
{
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;

    scanf ( "%d %d", &P, &Q ) ;

    solve () ;

    printf ( "%d", ++sol ) ;

    return 0;
}