#include <cstdio>
#define MAXN 500001
bool ciur[MAXN];
struct ches {
    int fact, pow;
};
ches putere[MAXN];

void ciuruim( ) {
    int i, j;
    for( i = 3 ; i * i <= MAXN ; i += 2 )
        for( j = i * i ; j <= MAXN ; j+= ( 2 * i ) )
            ciur[j] = 1;
}

void descomp( int &p, int q ) {
    int d = 3, put = 0, cp;
    while( p % 2 == 0 ) {
        ++put;
        p >>= 1;
    }

    if( p ) {
        ++putere[0].fact;
        putere[putere[0].fact].pow = put * q;
        putere[putere[0].fact].fact = 2;
    }
    cp = p;
    d = 3;
    while( d * d <= cp && p > 1 ) {
        if( ciur[d] == 0 ) {
            put = 0;
            while( p % d == 0 ) {
                ++put;
                p /= d;
            }

            if( put ) {
                ++putere[0].fact;
                putere[putere[0].fact].pow = d * q;
                putere[putere[0].fact].fact = d;
            }

            d += 2;
        }
    }
}

int pdfact( long long n, int d ) {
    int d1 = d, put = 0;
    while( d1 <= n ) {
        put += ( n / d1 );
        d1 *= d;
    }

    return put;

}

int main () {
    FILE *f, *g;

     f = fopen( "gfact.in", "r" );
     g = fopen( "gfact.out", "w" );

    int p, q, gasit, i;
    long long poz, pas, minim = 999999999999999999;

    fscanf( f, "%d%d", &p, &q );
    ciuruim( );
    descomp( p, q );

    poz = 0;
    pas = 1;
    pas <<= 29;

    while( pas ) {
        gasit = 1;
        i = 1;
        while( i <= putere[0].fact && gasit ) {
            if( pdfact( poz + pas, putere[i].fact ) < putere[i].pow )
                gasit = 0;
            ++i;
        }

        if( gasit == 1 && poz + pas < minim )
            minim = poz + pas;
        else if( gasit == 0 )
                poz += pas;

        pas >>= 1;
    }

    fprintf( g, "%lld\n", minim );

    fclose( f );
    fclose( g );

    return 0;

}