#include <fstream>
#include<limits.h>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
struct punct{
        int d;
        int e;
        }v[100001];
int i,t,k,b,n,u,nr,p;
long long s,Min;
int main()
{for(t=1;t<=10;t++){
    f>>n>>b;
    Min=LONG_LONG_MAX;
    nr=0;

for(i=2;i*i<=b;i++){
        if(b%i==0){
            nr++;
            v[nr].d=i;u=0;
                while(b%i==0){
                        b=b/i;
                            u++;}
                    v[nr].e=u;}
                    }
    if(b!=1){
        nr++;
            v[nr].d=b;
                v[nr].e=1;}

for(i=1;i<=nr;i++){
       p=v[i].d;

       s=0;

            while(p<=n){
                k=n/p;
                    s=s+1ll*(k-1)*(k)/2*p + 1ll*(k)*(n-(k)*p+1);
                    p=p*v[i].d;}
        if(s/v[i].e<Min)
            Min=s/v[i].e;}
    g<<Min<<'\n';}


    return 0;
}