#include <iostream>
#include <cstdio>
#include <vector>
#include <assert.h>
#include <algorithm>
#include <cmath>

using namespace std;

vector< pair<long long, long long> > power;

void factorization(long long n)
{
    long long tmp = n;
    for (long long i = 2; i * i <= tmp; ++i)
        if (n % i == 0)
        {
            n /= i;
            power.push_back(make_pair(i, 1));
            while (n % i == 0)
            {
                n /= i;
                power[power.size() - 1].second++;
            }
        }
    if (n > 1) 
        power.push_back(make_pair(n, 1));
}

int main()
{
    freopen("mars.in", "r", stdin);
    freopen("mars.out", "w", stdout);
    long long n, k;
    cin >> n >> k;
    assert(1 <= n && n <= 1e18);
    assert(2 <= k && k <= 1e9);   
    factorization(k);
    vector<long long> count(power.size());
    for (size_t i = 0; i < power.size(); ++i)
    {
        long long p = power[i].first;
        for (long long j = 1; j <= n / p; j *= p)
            count[i] += n / (j * p);
    }
    long long ans = count[0] / power[0].second;
    for (size_t i = 1; i < power.size(); ++i)
        ans = min(ans, count[i] / power[i].second);
    cout << ans << endl;
}
