#include<bits/stdc++.h>

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;

using namespace std;

vi primes;
int a[5020];
inline void gen_primes(int mx){
    int ok, cur = 3;
    primes.pb(2);
    while(cur < mx){
        ok = 1;
        for( int i = 0 ; i < primes.size() && primes[i] * primes[i] <= cur && ok ; ++i )
            if(cur % primes[i] == 0) ok = 0;
        if(ok) primes.pb(cur);
        cur += 2;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(0);
    int n , k , m , ans = INF;
    gen_primes(5012);
    cin >> n >> k;
    rep(i , primes.size()){
        a[primes[i]] = 0;
        m = n;
        while(m){
            a[primes[i]] += m / primes[i];
            m /= primes[i];
        }
        m = 0;
        while(k % primes[i] == 0){
            ++m;
            k /= primes[i];
        }
        if(m) ans = min(ans , a[primes[i]] / m);
    }
    dier(ans);
    return 0;
}