#include <fstream>

using namespace std;

ifstream fin ("zero2.in");
ofstream fout ("zero2.out");
long long n,b,i,nr,val,k,sol,s,t;
pair<long long,long long> v[105];
void descompune (long long b){

    long long d = 2;
    long long nr = b;
    while (d*d <= nr){
       long long e = 0;
        while (nr % d == 0){
            nr /= d;
            e++;
        }
        if (e != 0)
            v[++k] = make_pair (d,e);

        d++;
    }
    if (nr != 1)
        v[++k] = make_pair (nr,1);

}
int main (){

    /// numarul de zerouri ale numarului 1!*2!*...*n! in baza b
    /// este egal cu de cate ori se imparte nr la b.
    t = 10;
    for (;t--;){
        fin>>n>>b;
        /// il descompunem pe b in factori primi

        k = 0;
        descompune (b);

        sol = 2000000000000000000;
        for (i=1;i<=k;i++){
            nr = 1, s = 0;
            while (nr <= n/v[i].first){
                nr *= v[i].first;
                val = n/nr - 1;
                s += val*(val+1)/2*nr + (val+1)*(n- nr*(val+1)+1);
            }
            sol = min (sol,s/v[i].second);
        }
        fout<<sol<<"\n";

    }


    return 0;
}