#include<cstdio>
long long k,n,a,b,s1[1001],q,i,s,s2,n1,p,max=0,x,v[1001],vc[1001],min=2000000000,cate,ca;
int main ()
{
freopen("zero2.in","r",stdin);
freopen("zero2.out","w",stdout);
for(int co=1;co<=10;co++){
max=0;
for(i=1;i<=50;i++)
    v[i]=vc[i]=s1[i]=0;
cate=0;
ca=0;
s=0;
scanf("%lld%lld",&n1,&k);
p=2;
s2=0;
while(k!=1)
    {
    s=0;
    while(k%p==0)
        {
        k=k/p;
        s++;
        }
    if(s!=0)
       {
        v[++cate]=p;
        vc[cate]=s;
       }
    p++;
    }
s=0;
min=2000000000;
if(n1<=250000)
for(n=1;n<=n1;n++)
{
for(i=1;i<=cate;i++)
    {
    ca=v[i];
    while(ca<=n)
        {
        s1[i]+=n/ca;
        ca=ca*v[i];
        }
    }
}
for(i=1;i<=cate;i++)
    if(min>s1[i]/vc[i])
        min=s1[i]/vc[i];
s2+=min;
printf("%lld\n",s2);
}
return 0;
}