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

long long t,i,mini,n,b,e;
long long rez (long long n,long long i)
{
	long long rez=0,t,k;
	for(t=i;t<=n;t*=i){
		k=n/t;
		rez+=t*k*(k-1)/2+(n-k*t+1)*k;
	}
	return rez;
}

int main()
{
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);
	
	t=10;
	for(;t;--t){
		scanf("%ld%ld",&n,&b);
		mini=1LL<<61;
		for(i=2;i*i<=b;++i)
			if(b%i==0){
				e=0;
				while(b%i==0){
					++e;
					b/=i;
				}
			mini=min(mini,rez(n,i)/e);
		}
		if(b>1)
			mini=min(mini,rez(n,b));
		printf("%ld\n",mini);
	}
	return 0;
}