#include <iostream>
#include <map>

#define x first
#define y second
typedef long long LL;
using namespace std;

long long n, b;
map<LL, LL> m;
void resolve(long long n){
    for(LL i = 2; i * i <= n; ++ i){
        if(n % i == 0){
            while(n % i == 0){
                n /= i;
                m[i] ++;
            }
        }
    }
    if(n != 1){
        m[n] ++;
    }
}

int main(){
    cin >> n >> b;

    resolve(b);

    LL ans = 1LL << 62;
    for(auto factor : m){
        LL x = factor.x;
        LL y = factor.y;
        // cout << x << " " << y << endl; 
        LL s = 0;
        for(LL j = n; j; j /= x){
            s += j / x;
        }
        ans = min(ans, s / y);
    }
    cout << ans << endl;
    return 0;
}