#include <stdio.h>

typedef long long lint;

lint n,b,sol;

lint doit(lint x,lint p)
{
	lint c,r;
	c=x/p-1; r=x%p;
	return c*(c+1)/2*p+(c+1)*(r+1);
}

lint count(lint x,lint p)
{
	lint j,aux=0;
	for(j=p;j<=x;j*=p)
		aux+=doit(x,j);
	return aux;	
}

int main()
{
	lint i,j,x;
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);
	while(scanf("%lld %lld",&n,&b)==2)
	{
		sol=0;
		for(i=0;i<63;++i)
			sol|=1ll<<i;
		for(i=2;i*i<=b;++i)
		{
			for(j=0;b%i==0;b/=i,++j);
			if(!j)
				continue;
			x=count(n,i);
			if(x/j<sol)
				sol=x/j;
		}
		if(b!=1)
		{
			x=count(n,b);
			if(x<sol)
				sol=x;
		}
		printf("%lld\n",sol);		
	}
	return 0;
}