#include <bits/stdc++.h>
using namespace std;
long long ok(long long n, long long ii) {
  long long ret = 0;
  while (n > 0) {
    n /= ii;
    ret += n;
  }
  return ret;
}
long long n, b;
int main() {
  long long ans = LLONG_MAX;
  cin >> n >> b;
  for (long long i = 2; i * i <= b; i++) {
    if (b % i == 0) {
      long long times = 0;
      while (b % i == 0) {
        times++;
        b /= i;
      }
      ans = min(ans, ok(n, i) / times);
    }
  }
  if (b > 1) {
    ans = min(ans, ok(n, b));
  }
  cout << ans;
  return 0;
}
