#include <fstream>
using namespace std;
ifstream fin ("zero2.in");
ofstream fout("zero2.out");
long long n,B,minim,d,t=10,nr;
long long power(long long prim)
{
    long long sol=0;
    for(long long j=prim;j<=n;j*=prim)
    {
        long long k=n/j;
        sol+=(k*(k-1))/2*j+(n%j+1)*k;
    }
    return sol;
}
void solve()
{
    fin>>n>>B;
    minim=1e18;
    d=2;
    while(B>1)
    {
        nr=0;
        while(B%d==0)
        {
            B/=d;
            nr++;
        }
        if(nr>0)
           minim=min(minim,power(d)/nr);
        d++;
        if(d*d>B)
            d=B;
    }
    fout<<minim<<"\n";
}
int main()
{
    while(t--)
        solve();
    return 0;
}