#include <fstream>

#define ll long long
using namespace std;

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

const ll INF=(1LL<<62);

int nrP;
ll fact[20],putB[20],putP[20];

void desc(ll b)
{
    nrP=0;
    if(b%2==0)
    {
        fact[++nrP]=2;
        putB[nrP]=0;
        while(b%2==0)
        {
            putB[nrP]++;
            b/=2;
        }
    }
    for(ll d=3; d*d<=b; d+=2)
        if(b%d==0)
        {
            fact[++nrP]=d;
            putB[nrP]=0;
            do
            {
                putB[nrP]++;
                b/=d;
            }
            while(b%d==0);
        }
    if(b>1)
    {
        fact[++nrP]=b;
        putB[nrP]=1;
    }
}

void expp(ll N)
{
    for(int i=1; i<=nrP; i++)
    {
        ll pp=fact[i];
        putP[i]=0;
        while(N>=pp)
        {
            ll k=N/pp;
            putP[i]+=pp*k*(k-1)/2;
            putP[i]+=(N-k*pp+1)*k;
            if(pp>N/fact[i])
                break;
            pp*=fact[i];
        }
    }
}

int main()
{
    int t=10;
    while(t--)
    {
        ll N,B;
        f>>N>>B;
        desc(B);
        expp(N);
        ll rasp=INF;
        for(int i=1; i<=nrP; i++)
            if(putP[i]/putB[i]<rasp)
                rasp=putP[i]/putB[i];
        g<<rasp<<'\n';
    }
    f.close();
    g.close();
    return 0;
}