#include <bits/stdc++.h>
using namespace std;
inline long long Readin() {
  long long K = 0, F = 1;
  char C = ' ';
  while (C < '0' or C > '9') F = C == '-' ? -1 : 1, C = getchar();
  while (C <= '9' and C >= '0')
    K = (K << 1) + (K << 3) + C - '0', C = getchar();
  return F * K;
}
long long N;
inline long long Calc(long long B) {
  long long Ans = 0, T = (1.0 * log(N) / log(B));
  for (register long long i = 1, Bb = B; i <= T; ++i, Bb *= B) Ans += N / Bb;
  return Ans;
}
signed main() {
  N = Readin();
  if (N == 1) return not printf("0\n");
  long long B = Readin(), Ans = 1ll << 60;
  long long Nn = B;
  for (register long long i = 2, I = sqrt(Nn); i <= I; ++i)
    if (Nn % i == 0) {
      register long long Times = 0;
      while (Nn % i == 0) ++Times, Nn /= i;
      I = sqrt(Nn);
      Ans = min(Ans, Calc(i) / Times);
    }
  if (Nn > 1) Ans = min(Ans, Calc(Nn));
  return not printf("%lld\n", Ans);
}
