#include <bits/stdc++.h>

using namespace std;

ifstream fin("zero2.in");
ofstream fout("zero2.out");
typedef long long ll;
ll n, b, i, nrf, fact[102], ex[102], fr[102];

static inline ll Divizori(ll n, ll b) {
    ll rasp = LLONG_MAX;
    nrf = 0;

    ll d = 3, e = 0;
    while(b % 2 == 0) {
        e++;
        b /= 2;
    }
    if(e) {
        fact[++nrf] = 2;
        ex[nrf] = e;
    }
    while(d * d <= b) {
        if(b % d == 0) {
            e = 0;
            while(b % d == 0) {
                e++;
                b /= d;
            }

            fact[++nrf] = d;
            ex[nrf] = e;
        }
        d += 2;
    }
    if(b > 1) {
        fact[++nrf] = b;
        ex[nrf] = 1;
    }

    for(i = 1; i <= nrf; i++) {
        ll put = fact[i];
        ll fr = 0;
        while(put <= n) {
            e = n / put;
            fr += put * e * (e - 1) / 2;
            fr += e * (n - e * put + 1);
            put *= fact[i];
        }
        rasp = min(rasp, fr / ex[i]);
    }

    return rasp;
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    while(fin >> n >> b) {
        fout << Divizori(n, b) << "\n";
    }

    return 0;
}