#include <bits/stdc++.h>
using namespace std;
long long n, m, x, p[10005], s[10005], ans = 1000000000000000005;
long long npong(long long n, long long p) {
  long long ans = 0;
  while (n > 0) {
    n /= p;
    ans += n;
  }
  return ans;
}
signed main() {
  scanf("%lld%lld", &n, &m);
  for (long long i = 2; i * i <= m; i++) {
    while (m % i == 0) {
      p[x] = i;
      s[x]++;
      m /= i;
    }
    if (s[x]) x++;
  }
  if (m > 1) p[x] = m, s[x++] = 1;
  for (long long i = 0; i < x; i++) ans = min(ans, npong(n, p[i]) / s[i]);
  printf("%lld", ans);
  return 0;
}
