#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e5 + ;

pair<ll, ll> p[N];

int cnt;

ll C(ll x, ll p) {

    ll res = ;

    ll temp = p;

    while (x >= temp) {

        res += x / temp;

        if (x / p < temp) break;

        temp *= p;

    }

    return res;

}

int main() {

    ll n, b;

    scanf("%lld%lld", &n, &b);

    for (ll i = ; i * i <= b; i++) {

        if (b % i == ) {

            p[++cnt].first = i;

            p[cnt].second = ;

            while (b % i == ) { p[cnt].second++; b /= i; }

        }

    }

    if (b != ) { p[++cnt].first = b; p[cnt].second = ; }

    ll ans = 1e18;

    for (int i = ; i <= cnt; i++) {

        ll res = C(n, p[i].first);

        ans = min(ans, res / p[i].second);

    }

    cout << ans << '\n';

    return ;

}