#include <fstream>
#include <limits.h>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
long long n, b, p, put, i, l, minp, putfact, k, ok;
int main()
{
    for (l=1; l<=10; l++)
    {
        f>>n>>b;
        minp=LLONG_MAX;
        for (i=2; i*i<=b; i++)
        {
            ok=0;
            put=0;
            putfact=0;
            while (b%i==0)
            {
                put++;
                b/=i;
                ok=1;
            }
            if(ok==1)
            {
                p=i;
                while (p <= n)
                {
                    k=n/p-1;
                    putfact+=k*(k+1)/2*p + (k+1)*(n-(k+1)*p+1);
                    p*=i;
                }
                if (minp > putfact/put)
                    minp = putfact/put;
            }
        }
        if (b!=1)
        {
            putfact=0;
            p=b;
            while (p <= n)
            {
                k=n/p-1;
                putfact+=k*(k+1)/2*p + (k+1)*(n-(k+1)*p+1);
                p*=b;
            }
            if (minp > putfact)
                minp = putfact;
        }
        g<<minp<<"\n";
    }
    return 0;
}