#include<fstream>
using namespace std;
#include<limits.h>
int main()
{
	ifstream fcin("zero2.in");
	ofstream fcout("zero2.out");
	long long t=10,n,b,i,f,pt,min,pt2,f2,k;
	while(t--)
	{
		min=LONG_LONG_MAX;
		fcin>>n>>b;
		for(f=2;f*f<=b;f++)
		{
			pt=0;
			while(b%f==0)
				b/=f,pt++;
			if(pt)
			{
				k=n/f-1;
				pt2=0;
				for(f2=f;f2<=n;f2*=f,k=n/f2-1)
					pt2=pt2+k*(k+1)/2*f2+(k+1)*(n-(k+1)*f2+1);
				if(pt2/pt<min)
					min=pt2/pt;
			}
		}
		if(b>1)
		{
			pt=1;
			pt2=0;
			k=n/b-1;
			for(f2=b;f2<=n;f2*=b,k=n/f2-1)
				pt2=pt2+k*(k+1)/2*f2+(k+1)*(n-(k+1)*f2+1);
			if(pt2/pt<min)
				min=pt2/pt;
		}
		fcout<<min<<"\n";
	}
	return 0;
}