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

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

long long p, q, copie, expo, k, poz;

struct descompunere{
    long factor;
    long expo;
} descP[100];

void descompunereFactoriPrimi(){
    copie = p;
    expo = 0;

    while(copie % 2 == 0){
        expo++;
        copie /= 2;
    }

    if(expo > 0){
        descP[++k].factor = 2;
        descP[k].expo = expo * q;
    }

    for(int i = 3; i <= sqrt(copie); i += 2){
        expo = 0;
        while(copie % i == 0){
            expo++;
            copie /= i;
        }

        if(expo > 0){
            descP[++k].factor = i;
            descP[k].expo = expo * q;
        }
    }

    if(copie > 2){
        descP[++k].factor = copie;
        descP[k].expo = q;
    }
}

long long putere(long long factor,long long nr){

    long long power = factor, rez = 0;
    while(power <= nr){
        rez += nr / power;
        power *= factor;
    }
    return rez;
}

bool esteOk(long long x){

   for(int i = 1; i <= k; ++i)
        if(descP[i].expo > putere(descP[i].factor, x))
            return 0;
    return 1;
}

int main()
{
    in>>p>>q;

    descompunereFactoriPrimi();

    long long stg = 1;
    long long drp = ((long long) 1<<50);

    while(stg <= drp){
        long long mij = (drp + stg) / 2;

        if(esteOk(mij)){
            poz = mij;
            drp = mij - 1;
        }

        else stg = mij + 1;
    }

    out<<poz;
    return 0;
}