#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
const long long inf = 1e18;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n, b;
  map<long long, long long> pw;
  cin >> n >> b;
  for (long long i = 2; i * i <= b; i++) {
    while (b % i == 0) {
      b /= i;
      pw[i]++;
    }
  }
  if (b > 1) {
    pw[b]++;
  }
  auto f = [&](long long n, long long p) {
    long long ans = 0;
    while (n > 0) {
      ans += n / p;
      n /= p;
    }
    return ans;
  };
  long long ans = inf;
  for (auto &[p, k] : pw) {
    ans = min(ans, f(n, p) / k);
  }
  cout << ans;
}
