#include<cstdio>
using namespace std;
long long c,n,b,r,x,pt,d,it,i,s,cr;
int main()
{
    freopen("zero2.in","r",stdin);
    freopen("zero2.out","w",stdout);

    for(it=1;it<=10;it++)
    {
        scanf("%lld %lld",&n,&b);
        x=b;
        d=2;
        while(d*d<=x)
        {
            c=0;
            while(x%d==0)
            {
                c++;
                x/=d;
            }
            if(c>0)
            {
                cr=c;
                r=d;
            }
            d++;
        }
        if(x!=1)
        {
            cr=1;
            r=x;
        }
        pt=0;
        for(i=r;i<=n;i++)
        {
            s=0;
            x=i;
            while(x>0)
            {
                x/=r;
                s+=x;
            }
            pt+=s;
        }
        printf("%lld\n",pt/cr);

    }
    return 0;
}