#include <stdio.h>
long long div[10],pdiv[10],nrdiv;

long long putere(long long n,long long p){
    long long pp=p,t=0;

    while(pp<=n){
        t+=n/pp;
        pp*=p;
    }
    return t;
}

void descompunere(long long n){
    long long d,p;

    d=2;
    while(d*d<=n){
        p=0;
        while(n%d==0){
            p++;
            n/=d;
        }
        if(p>0){
            div[nrdiv]=d;
            pdiv[nrdiv++]=p;
        }
        d++;
    }
    if(n>1){
        div[nrdiv]=n;
        pdiv[nrdiv++]=1;
    }
}

int main(){
    FILE *fin=fopen("gfact.in","r");
    FILE *fout=fopen("gfact.out","w");
    long long p,q,i,j,pas;

    fscanf(fin,"%lld%lld",&p,&q);
    descompunere(p);
    pas=1;
    for(i=0; i<50; i++)
        pas*=2;
    i=0;
    while(pas!=0){
        for(j=0; j<nrdiv; j++)
            if(putere(i+pas,div[j])<pdiv[j]*q)
                i+=pas;
        pas/=2;
    }
    fprintf(fout,"%lld\n",i+1);
    fclose(fin);
    fclose(fout);
    return 0;
}