#include <bits/stdc++.h>
using namespace std;
const long long inf = 1000000000000000009;
int main() {
  long long n, b, x, now, cnt, k, then;
  cin >> n >> b;
  long long ans = inf;
  for (long long i = 2; i * i <= b; i++) {
    if (b % i == 0) {
      cnt = 0;
      while (b % i == 0) b /= i, cnt++;
      x = n;
      now = 0;
      then = 0;
      while (x > 0) now += (x / i), x /= i;
      then = now / cnt;
      ans = min(ans, then);
    }
  }
  if (b >= 2) {
    x = n;
    now = 0;
    while (x > 0) now += (x / b), x /= b;
    ans = min(ans, now);
  }
  cout << ans << endl;
}
