#include <bits/stdc++.h>
using namespace std;
long long n, mod, cnt;
long long num[10000000 + 10], sum[10000000 + 10];
int main() {
  scanf("%I64d%I64d", &n, &mod);
  long long x = mod;
  for (long long i = 2; i <= sqrt(mod); i++) {
    if (!x) break;
    if (x % i == 0) {
      num[++cnt] = i;
      while (x % i == 0 && x) {
        x /= i;
        sum[cnt]++;
      }
    }
  }
  if (x != 1) {
    num[++cnt] = x;
    sum[cnt] = 1;
  }
  long long ans = 1e18;
  for (long long i = 1; i <= cnt; i++) {
    long long k = n, s = 0, l = num[i];
    while (k) {
      k /= l;
      s += k;
    }
    ans = min(ans, s / sum[i]);
  }
  printf("%I64d\n", ans);
  return 0;
}
