#include <fstream>
#include <cmath>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
long long N,B;
long long Result;
long long Answer=10000000000000;
long long Prime[35000],Exp[35000],ind;
void Descomp()
{
    long long i=2;
    long long limit=(long long)sqrt((double)B);
    while(B>1 && i<=limit)
    {
        if(B%i==0)
        {
            Prime[++ind]=i;
            Exp[ind]=0;
        }
        while(B%i==0)
            B/=i,Exp[ind]++;
        ++i;
    }
    if(B!=1)
    {
        Prime[++ind]=B;
        Exp[ind]=1;
    }
}
void Solve(long long k)
{
    long long aux=N/k;
    Result+=(aux)*(aux-1)/2*k;
    Result+=aux*(N%k+1);
}
void Browse()
{
    long long i;
    for(i=1;i<=ind;i++)
    {
        Result=0;
        long long fact=Prime[i];
        while(fact<=N)
        {
            Solve(fact);
            fact*=Prime[i];
        }
        Answer=min(Answer,Result/Exp[i]);
    }
    g<<Answer<<"\n";
}
int main()
{
    int T=10;
    while(T--)
    {
        f>>N>>B;
        ind=0;
        Answer=10000000000000;
        Result=0;
        Descomp();
        Browse();
    }
    return 0;
}