#include<fstream>
#include<algorithm>
 
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
long long t,i,mini,n,b,e;
long long rez(long long n,long long i)
{long long rez=0,t,k;
for(t=i;t<=n;t*=i)
{k=n/t;
rez+=t*k*(k-1)/2+(n-k*t+1)*k;
}
return rez;
}
int main()
{t=10;
for(;t;--t)
{f>>n>>b;
mini=1LL <<61;
for(i=2;i*i<=b;++i)
    if(b%i==0)
    {e=0;
    while(b%i==0)
    {++e;
    b/=i;
    }
    mini=min(mini,rez(n,i)/e);
    }
if(b>1)
    mini=min(mini,rez(n,b));
g<<mini<<'\n';
}
return 0;
}