#define ll long long
const ll maxn = 1e6+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double pi = acos(-1.0);
const ll inf = 0x3f3f3f3f;

ll n, b;
ll prime[maxn];
vector<ll>ve;

void init(){
    for(ll i = 2; i <= 1000000; i++){
        if (!prime[i]){
            ve.push_back(i);
            for(ll j = 2*i; j <= 1000000; j += i){
                prime[j] = 1;
            }
        }
    }
}
ll get(ll pp, ll x){
    ll res = 0;
    
    while(x){
        res += x/pp;
        x /= pp;
    }
    return res;
}

ll cnt[maxn], num[maxn];
void solve(){
    ll f = b;
    for(ll i = 0; i < ve.size(); i++){
        if (f == 1) break;
        while(f%ve[i] == 0){
            cnt[ve[i]]++;
            f /= ve[i];
        }        
    }
    for(ll i = 0; i < ve.size(); i++){
        if (cnt[ve[i]]){
            num[ve[i]] = get(ve[i], n);
        }
    }
    ll ans = 1e18+10;
    if (f != 1) ans = min(ans, get(f, n));
    for(ll i = 0; i < ve.size(); i++){
        if (cnt[ve[i]]){
            ans = min(ans, num[ve[i]]/cnt[ve[i]]);
        }
    }
    cout << ans << endl;
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> b;
    init();
    solve();
    return 0;
}