#include<stdio.h>

FILE*f=fopen("zero2.in","r");
FILE*g=fopen("zero2.out","w");

long long N,B,i,e,T;
long long sol;

long long min(long long a,long long b){
	if ( a < b )
		return a;
	return b;
}

long long S(long long N,long long p){
	long long k = N / p - 1;
	long long aux;
	
	aux = k * (k+1) / 2 * p  + ( k + 1 ) * ( N - ( k + 1 ) * p + 1 );
	
	return aux;
}

long long Nr(long long N,long long p){
	long long aux = p;
	long long REZ = 0;
	while ( p <= N ) {
		REZ += S(N,p);
		p *= aux;
	}
	return REZ;
}

int main () {
	
	for ( T = 1 ; T <= 10 ; ++T ){
		fscanf(f,"%lld %lld",&N,&B);
		sol = 1LL << 62;
		for ( i = 2 ; i * i <= B ; ++i ){
			e = 0;
			while ( B % i == 0 ){
				++e;
				B /= i;
			}
			if ( e )
				sol = min(sol,Nr(N,i) / e );
		}
		if ( B > 1 )
			sol = min(sol,Nr(N,B));
		fprintf(g,"%lld\n",sol);
		
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}