#include <fstream>

using namespace std;

typedef unsigned long long type;

const char InFile[]="zero2.in";
const char OutFile[]="zero2.out";
const int TestCount=10;
const type MAX=1LL<<63;

ifstream fin(InFile);
ofstream fout(OutFile);

type N,B;

inline type S(type N,type p)
{
	type k=N/p-1;
	return ((k*(k+1))>>1)*p+((k+1)*(N-(k+1)*p+1));
}

inline type Nr(type N,type p)
{
	type x=p;
	type s=S(N,x);
	type sol(0);
	while(s)
	{
		sol+=s;
		x=x*p;
		s=S(N,x);
	}
	return sol;
}

int main()
{
	for(register int t=0;t<TestCount;++t)
	{
		fin>>N>>B;
		type k=0;
		type sol;
		if(B%2==0)
		{
			while(B%2==0){B>>=1;++k;}
			sol=Nr(N,2)/k;
		}
		else
		{
			sol=MAX;
		}
		for(type i=3;i*i<=B;i+=2)
		{
			if(B%i==0)
			{
				k=0;
				while(B%i==0){B/=i;++k;}
				sol=min(sol,Nr(N,i)/k);
			}
		}
		if(B>1)
		{
			sol=min(sol,Nr(N,B));
		}
		fout<<sol<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}