#include<stdio.h>
#include<math.h>
#include<limits.h>
FILE *f=fopen("zero2.in","r"), *g=fopen("zero2.out","w");

long int N, B;
long long int R;

void introdu( long int b, long int e ){
long int i, putere, Np;
long long int nr=0;

    putere=1; Np= N/putere;
    while( N/putere >= b ){

        putere*=b; Np= N/putere;

        nr=nr - 1LL * putere * Np * (Np+1) /2 + 1LL * (N+1) * (N/putere);

    }   //fprintf(g,"N=%ld b=%ld >> %lld\n",N,b,nr);

    nr/=(1LL*e);

    if( nr<R ){ R=nr; }

}

void rezolva(){
long int i, baza, exponent, radical;

    R=LONG_LONG_MAX;
    radical = sqrt(B);

    for(i=2;i<=radical;i++){

        if( B%i==0 ){

            baza=i; exponent=0;
            while( B%i==0 ){ B/=i; exponent++; }

            introdu( baza, exponent );

        }

    }
    if( B>1 ) introdu( B, 1 );

}

int main(){

    for(long int test=1;test<=10;test++){
        fscanf(f,"%ld %ld\n",&N,&B);
        rezolva();
        fprintf(g,"%lld\n",R);
    }

return 0;
}