#include <fstream>
#include <limits.h>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
int t,n,b,nr,d;
long long p,Min,k;
int main()
{
    t=10;
    while(t){
        f>>n>>b;
        Min=LONG_LONG_MAX;
        for(d=2;d*d<=b;d++)
            if(b%d==0){
                nr=0;
                while(b%d==0){
                    nr++;
                    b/=d;
                }
                k=d;
                p=0;
                while(k<=n){
                    p+=(n/k-1)*(n/k)/2*k+(n%k+1)*(n/k);
                    k*=d;
                }
                Min=min(Min,p/nr);
            }
        if(b!=1){
            k=b;
            p=0;
            while(k<=n){
                p+=(n/k-1)*(n/k)/2*k+(n%k+1)*(n/k);
                k*=b;
            }
            Min=min(Min,p);
        }
        g<<Min<<'\n';
        t--;
    }
    return 0;
}