#include<fstream>

using namespace std;

ifstream f("zero2.in");
ofstream g("zero2.out");

typedef long long int6;

int6 n,b,i,j,k,pr[100],e[100],t,p,r,maxt;

int6 S(int6 n,int6 p)
{
    int6 k=n/p;
    --k;
    return k*(k+1)/2*p+(k+1)*(n-(k+1)*p+1);
}

int main()
{
    t=10;
    for(p=1;p<=t;++p)
    {
        f>>n>>b;
        k=0;
        for(i=2;i*i<=b;++i)
            if(b%i==0)
            {
                pr[++k]=i;
                e[k]=0;
                while(b%i==0)
                    b/=i,++e[k];
            }
        if(b>1)
            pr[++k]=b,e[k]=1;
        maxt=(1LL<<63)-1;
        for(i=1;i<=k;++i)
        {
            r=0;
            j=pr[i];
            while(j<=n)
                r+=S(n,j),j*=pr[i];
            r/=e[i];
            if(r<maxt)
                maxt=r;
        }

        g<<maxt<<"\n";
    }

    f.close();
    g.close();

    return 0;
}