#include <bits/stdc++.h>

using namespace std;

ifstream fin("zero2.in");
ofstream fout("zero2.out");
int n, b;

static inline int Exponent(int n, int d) {
    int nm = 0, put = d;
    while(put <= n) {
        nm += n / put;
        put *= d;
    }
    return nm;
}

static inline int PiFact(int n, int d, int e = 1) {
    int nm = 0;
    for(int i = 2; i <= n; i++) {
        nm += Exponent(i, d);
    }
    return nm / e;
}

static inline int Divizori(int n, int b) {
    int rasp = INT_MAX;

    int d = 3, e = 0;
    while(b % 2 == 0) {
        e++;
        b /= 2;
    }
    if(e) rasp = min(rasp, PiFact(n, 2, e));
    while(d * d <= b) {
        if(b % d == 0) {
            e = 0;
            while(b % d == 0) {
                e++;
                b /= d;
            }

            rasp = min(rasp, PiFact(n, d, e));
        }
        d += 2;
    }
    if(b > 1) rasp = min(rasp, PiFact(n, b, 1));

    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;
}