#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("zero2.in");
ofstream fout("zero2.out");
ll t = 10, n, b;
vector < pair <ll, ll> > v;

void desc() {
    ll div = 2, a = b;
    while (a > 1) {
        ll p = 0;
        while (a % div == 0)
            a /= div, ++p;
        if (p > 0)
            v.push_back({div, p});
        ++div;
        if (a > 1 && div * div > a)
            div = a;
    }
    return;
}

ll aflaPutere(ll nr) {
    ll put = 0, dim = 2;
    while (dim * nr - 1 <= n) {
        put = put * (dim - 1) + (dim * nr - 1 - (dim - 1) * nr + 1) * (dim - 1);
        ++dim;
    }
    if ((dim - 1) * nr <= n)
        put += (n - (dim - 1) * nr + 1) * (dim - 1);
    return put;
}

int main() {
    //cin >> n >> b;
    //cout << aflaPutere(b);
    //return 0;
    while (t--) {
        fin >> n >> b;
        desc();
        ll rez = 1e12;
        while (!v.empty()) {
            ll put = aflaPutere(v.back().first);
            rez = min(rez, put / v.back().second);
            v.pop_back();
        }
        fout << rez << "\n";
    }
    return 0;
}