#include<fstream>

using namespace std;

#include<limits.h>

ifstream fcin("zero2.in");
ofstream fcout("zero2.out");

int main()
{

    long long t=10,n,b,i,f,pt,min,pt2,f2,k;
    while(t--)
    {
        min=LONG_LONG_MAX;
        fcin>>n>>b;
        for(f=2;f*f<=b;f++)
        {
            pt=0;
            while(b%f==0)
                b/=f,pt++;
            if(pt)
            {
                k=n/f-1;
                pt2=0;
                for(f2=f;f2<=n;f2*=f,k=n/f2-1)
                    pt2=pt2+k*(k+1)/2*f2+(k+1)*(n-(k+1)*f2+1);
                if(pt2/pt<min)
                    min=pt2/pt;
            }
        }
        if(b>1)
        {
            pt=1;
            pt2=0;
            k=n/b-1;
            for(f2=b;f2<=n;f2*=b,k=n/f2-1)
                pt2=pt2+k*(k+1)/2*f2+(k+1)*(n-(k+1)*f2+1);
            if(pt2/pt<min)
                min=pt2/pt;
        }
        fcout<<min<<"\n";
    }
    return 0;
}