#include <stdio.h>
#include <stdlib.h>

int b[10], exp[10];

long long putere( long long p, long long nr ) {
    long long i, nrc = 0;
    for ( i = p; i <= nr; i *= p )
        nrc += ( nr / i );
    return nrc;
}

int verificare( long long nr ) {
    int i = 0;
    while ( b[i] != 0 ) {
        if ( putere( b[i], nr ) < exp[i] )
            return 0;
        i++;
    }
    return 1;
}

long long cautareBinara( ) {
    long long r = 0, pas = 1LL << 60;
    while ( pas != 0 ) {
        if ( verificare( r + pas ) == 0 )
            r += pas;
        pas /= 2;
    }
    return r + 1;
}

int main() {
    FILE *fin, *fout;
    int p, q, d, i;
    long long fact;
    fin = fopen( "gfact.in", "r" );
    fout = fopen( "gfact.out", "w" );
    fscanf( fin, "%d%d", &p, &q );
    d = 2;
    i = 0;
    while ( d * d <= p ) {
        if ( p % d == 0 ) {
            b[i] = d;
            while ( p % d == 0 ) {
                p /= d;
                exp[i]++;
            }
            exp[i] *= q;
            i++;
        }
        d++;
    }
    if ( p > 1 ) {
        b[i] = p;
        exp[i] = q;
    }
    fact = cautareBinara();
    i = 2;
    while ( fact > 1 ) {
        fact /= i;
        i++;
    }
    fprintf( fout, "%d", i );
    fclose( fin );
    fclose( fout );
    return 0;
}