#include <fstream>
#include <vector>
using namespace std;

ifstream fin ("zero2.in");
ofstream fout ("zero2.out");

typedef long long ull;

const ull oo = 1e15;

int pasi = 10;

vector <pair <ull, ull> > prim;
vector <pair <ull, ull> > f;
ull n, b;

int main() {
    while (pasi--) {
        ull sol = oo;
        vector <pair <ull, ull> >().swap(prim);
        vector <pair <ull, ull> >().swap(f);
        fin >> n >> b;
        if (b % 2 == 0) {
            prim.push_back (make_pair (2, 0));
            while (b % 2 == 0) {
                prim.back().second++;
                b >>= 1;
            }
        }
        ull aux = b;
        for (int i = 3; i * i <= b && aux != 1; i += 2)
            if (aux % i == 0) {
                prim.push_back (make_pair (i, 0));
                while (aux % i == 0) {
                    prim.back().second++;
                    aux /= i;
                }
            }
        if (aux != 1)
            prim.push_back (make_pair (aux, 1));
        for (int i = 0; i < prim.size(); ++i) {
            f.push_back (make_pair (prim[i].first, 0));
            ull nr = f.back().first;
            while (nr <= n) {
                f.back().second += (n / nr - 1) * (n / nr) / 2 * nr + ((n + 1 - nr) % nr ? ((n + 1 - nr) % nr) * (n / nr) : n / nr * nr);
                nr *= f.back().first;
            }
        }
        for (int i = 0; i < prim.size(); ++i)
            sol = min(sol, f[i].second / prim[i].second);
        fout << sol << "\n";
    }
}