#include <bits/stdc++.h>
using namespace std;
const int MAXN = -1;
const long long INF = (long long)1e18 + 50;
map<long long, int> F;
void fact(long long n) {
  F.clear();
  for (long long p = 2; p * p <= n; p++) {
    while (n % p == 0) F[p]++, n /= p;
  }
  if (n > 1) F[n]++;
}
long long countp(long long n, long long p) {
  long long ans = 0;
  while (n >= p) ans += n / p, n /= p;
  return ans;
}
long long n, b;
int main() {
  while (scanf("%lld %lld", &n, &b) >= 1) {
    fact(b);
    long long ans = INF;
    for (auto t : F) {
      long long p = t.first, e = t.second;
      long long c = countp(n, p);
      ans = min(ans, c / e);
    }
    printf("%lld\n", ans);
  }
  return 0;
}
