#include <bits/stdc++.h>
using namespace std;
using llong = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    llong n, k;
    cin >> n >> k;

    llong zeros = LLONG_MAX;

    for (auto i = 2; i <= k; i++)
    {
        if (!(k % i))
        {
            llong c = 0;
            while (!(k % i))
            {
                c++;
                k /= i;
            }
            llong c_2 = 0;
            llong d = n;
            while (d / i > 0)
            {
                c_2 += d / i;
                d /= i;
            }
            zeros = min(zeros, c_2 / c);
        }
    }

    cout << zeros;

    return 0;
}