#include<fstream>
#include<algorithm>

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

long long t,i,mini,n,b,e;

long long rez(long long n,long long i)
{
    long long rez=0,t,k;
    for(t=i;t<=n;t*=i)
    {
        k=n/t;
        rez+=t*k*(k-1)/2+(n-k*t+1)*k;
    }
    return rez;
}

int main()
{
    t=10;
    for(;t;--t)
    {
        f>>n>>b;
        mini=1LL <<61;
        for(i=2;i*i<=b;++i)
            if(b%i==0)
            {
                e=0;
                while(b%i==0)
                {
                    ++e;
                    b/=i;
                }
                mini=min(mini,rez(n,i)/e);
            }
        if(b>1)
        mini=min(mini,rez(n,b));
        g<<mini<<'\n';
}
return 0;
}