#include <bits/stdc++.h>
const long long INF = 0x3f3f3f3f3f3f3f3f;
long long N, b;
long long p[25];
int e[25], cnt;
long long Ans = INF;
int main() {
  scanf("%I64d%I64d", &N, &b);
  for (long long i = 2; i * i <= b; ++i)
    if (b % i == 0) {
      p[++cnt] = i, e[cnt] = 0;
      while (b % i == 0) b /= i, ++e[cnt];
    }
  if (b > 1) p[++cnt] = b, e[cnt] = 1;
  for (int i = 1; i <= cnt; ++i) {
    long long num = 0, m = N;
    while (m) num += m / p[i], m /= p[i];
    Ans = std::min(Ans, num / e[i]);
  }
  printf("%I64d\n", Ans);
  return 0;
}
