#include <stdio.h>
#define N 100000
#define MAX 999999999999999
int div[N],power[N];
int main()
{
    FILE *fin,*fout;
    fin=fopen("zero2.in","r");
    fout=fopen("zero2.out","w");
    int t=10;
    while(t){
        int n,b;
        fscanf(fin,"%d%d",&n,&b);
        int nr=0,i=2;
        while(i*i<=b){
            int put=0;
             while(b%i==0){
                    b=b/i;
                    put++;
            }
            if(put!=0){
                div[++nr]=i;
                power[nr]=put;
            }
            i++;
        }
        if(b!=1){
            div[++nr]=b;
            power[nr]=1;
        }
        long long zmin=MAX;
        for(i=1; i<=nr; i++){
            long long cdiv=div[i],s=0;
            while(cdiv<=n){
                long long k=n/cdiv;
                s=s+(k-1)*k/2*cdiv+k*(n-k*cdiv+1);
                cdiv=cdiv*div[i];
            }
            if(s/power[i]<=zmin)
                zmin=s/power[i];
        }
        fprintf(fout,"%lld\n",zmin);
        t--;
    }
    return 0;
}