#include <iostream>
#include <fstream>
#define INF 2000000000
using namespace std;
ifstream si("zero2.in");
ofstream so("zero2.out");
int main()
{
    int n,b;
    long long minn;
    for(int q=0;q<10;++q)
    {
        si>>n>>b;
        minn=INF;
        for(int d=2;d*d<=b;++d)
            if(b%d==0)
            {
                int nr=0;
                long long p,q=0;
                while(b%d==0)
                {
                    ++nr;
                    b/=d;
                }
                for(long long i=d;i<=n;i*=d)
                {
                    p=n/i;
                    q+=p*(p-1)/2*i+(n-p*i+1)*p;
                }
                minn=min(minn,q/nr);
            }
        if(b>1)
        {
            long long p,q=0;
            for(long long i=b;i<=n;i*=b)
            {
                p=n/i;
                q+=p*(p-1)/2*i+(n-p*i+1)*p;
            }
            minn=min(minn,q);
        }
        so<<minn<<"\n";
    }
    return 0;
}