#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef string str;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define forr(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, r, l) for (int i = (int)(r); i >= (int)(l); --i)

#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)

ll legendre(ll n, ll p) {
    ll cnt = 0;
    while (n > 0) {
        cnt += n / p;
        n /= p;
    }
    return cnt;
}

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

    

    ll n, m;
    if (cin >> n >> m) {
        if (m == 1) {
            cout << 0 << "\n";
            return 0;
        }

        ll ans = 1e18;
        ll temp = m;

        for (ll i = 2; i * i <= temp; ++i) {
            if (temp % i == 0) {
                ll e = 0;
                while (temp % i == 0) {
                    e++;
                    temp /= i;
                }
                ll cnt = legendre(n, i);
                cmin(ans, cnt / e);
            }
        }

        if (temp > 1) {
            ll cnt = legendre(n, temp);
            cmin(ans, cnt / 1);
        }

        cout << ans << "\n";
    }

    return 0;
}