#include <bits/stdc++.h>

#define MaxN 1000005
#define INF 2140000000
#define MOD 1000000007

using namespace std;

FILE*IN,*OUT;

long long Ans=0,N,B,fact[MaxN],Pow[MaxN],Min=-1,Size=0;
void Factorize(long long val)
{
    for(long long i=2;i<=val;i++)
    {
        if(i*i>val)
            i=val;
        if(val%i==0)
        {
            fact[++Size]=i;
            while(val%i==0)
                Pow[Size]++,val/=i;
        }
    }
}
long long Solve(long long D)
{
    long long L=N/D-1;
    return D*L*(L+1)/2+(L+1)*(N-(L+1)*D+1);
}
int main()
{
    IN=fopen("zero2.in","r");
    OUT=fopen("zero2.out","w");

    for(int t=1;t<=10;t++)
    {
        memset(fact,0,sizeof fact);
        memset(Pow,0,sizeof Pow);
        Size=0;
        Min=-1;
        fscanf(IN,"%lld%lld",&N,&B);
        Factorize(B);
        for(int i=1;i<=Size;i++)
        {
            long long Act=0,aux=fact[i];
            while(aux<=N)
                Act+=Solve(aux),aux*=fact[i];
            if(Min==-1)
                Min=Act/Pow[i];
            else Min=min(Min,Act/Pow[i]);
        }
        fprintf(OUT,"%lld\n",Min);
    }

    return 0;
}