#include <fstream>

using namespace std;

ifstream fin ("zero2.in");
ofstream fout ("zero2.out");

long long d[100010],p[100010],m,x,Div,i,j,n,b,nc,y;
long long minim, sol,a;


int main () {

    x=10;
    while (x--) {
        fin>>n>>b;

        for (i=1;i<=Div;i++)
            d[i]=p[i]=0;
        Div=0;
        a=b;
        for (i=2;i*i<=a;i++) {
            if (b%i==0) {
                d[++Div]=i;
                while (b%i==0){
                    p[Div]++;
                    b/=i;
                }
            }
        }
        if (b!=1){
            d[++Div]=b;
            p[Div]=1;
        }
        minim=(1LL<<62);
        for (i=1;i<=Div;i++) {
            sol=0;
            for (j=d[i];j<=n;j*=d[i]) {
                y=n/j;
                y=y*(y-1)/2*j+(n+1-y*j)*y;
                sol+=y;
            }
            sol/=p[i];
            if (sol<minim)
                minim=sol;
        }


        fout<<minim<<"\n";
    }


    return 0;

}