#include<fstream>
#include<cmath>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
long long int calc(long long int n,long long int p)
{
    long long int k,sol=0;
    for(long long int x=p;x<=n;x*=p)
    {
        k=n/x-1;
        sol+=k*(k+1)*x/2+(k+1)*(n-(k+1)*x+1);
    }
    return sol;
}
int main()
{
    int t=10;
    long long int n,b,ans,k;
    while(t--)
    {
        f>>n>>b;
        ans=1<<63;
        for(int i=2;i*i<=b;i++)
        {
            if(b%i==0)
            {
                k=0;
                while(b%i==0)
                {
                    b/=i;
                    k++;
                }
                ans=min(ans,calc(n,i)/k);
            }
        }
        if(b>1)
          ans=min(ans,calc(n,b));
        g<<ans<<"\n";
    }
    return 0;
}