#include <fstream>
using namespace std;
ifstream fin ("zero2.in");
ofstream fout ("zero2.out");
const long long INF = 1LL << 62;///infinit
int fp[15], ex[15], nf;
long long expf[15];
void desc (int n)
{
    nf=0;
    for (int d=2;d*d<=n;d++)
        if (n%d==0)
        {
            nf++;
            fp[nf]=d;
            ex[nf]=0;
            do
            {
                ex[nf]++;
                n/=d;
            }
            while (n%d==0);
        }
    if (n>1)
    {
        nf++;
        fp[nf]=n;
        ex[nf]=1;
    }
}

void expp (int n)
{
    for (int i=1; i<=nf;i++)
    {
        long long pp=fp[i];
        expf[i]=0;
        while (n>=pp)
        {
            int k=n/pp;
            expf[i]+=pp*k*(k - 1)/2;
            expf[i]+=(n-k*pp+1)*k;
            pp*=fp[i];
        }
    }
}
int main()
{
    int n,b,t=10;
    long long nrz;
    while (t--)
    {
        fin>>n>>b;
        desc (b);
        expp (n);
        nrz = INF;
        for (int i=1;i<=nf;i++)
            nrz=min (nrz,expf[i]/ex[i]);
        fout << nrz << '\n';
    }
    return 0;
}