#include <cstdio>
#include <iostream>
#define INF 9223372036854775807
using namespace std;
pair <long long,long long> fact [100];
int main()
{
    FILE *fin=fopen ("zero2.in","r");
    FILE *fout=fopen ("zero2.out","w");
    long long k,n,b,sol,s,d,nr,div,i;
    for (int kk=1;kk<=10;kk++){
        //if (kk==3)
          //  printf ("a");
        fscanf (fin,"%lld%lld",&n,&b);
        s=n*(n+1)/2;
        d=2;
        div=0;
        while (d*d<=b){
            if (b%d==0){
                div++;
                fact[div].first=d;
                fact[div].second=0;
                while (b%d==0){
                    b/=d;
                    fact[div].second++;
                }
            }
            d++;
        }
        if (b!=1){
            div++;
            fact[div]=make_pair (b,1);
        }
        sol=INF;
        for (i=1;i<=div;i++){
            nr=1;
            s=0;
            while (nr<=n/fact[i].first){
                nr=nr*fact[i].first;
                k=n/nr-1;
                s+=k*(k+1)/2*nr + (k+1)*(n-(k+1)*nr+1);
            }
            sol=min(sol,s/fact[i].second);
        }
        fprintf (fout,"%lld\n",sol);
    }
    return 0;
}