#include<fstream>
#include<algorithm>

using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
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()
{t=10;
for(;t;--t)
{f>>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));
g<<mini<<'\n';
}
return 0;
}