#include <bits/stdc++.h>
using namespace std;
long long n, b, p[1000000], num[1000000], tot;
int main() {
  cin >> n >> b;
  long long t, s, ans = 10e18;
  for (long long i = 2; i * i <= b; i++) {
    if (b % i != 0) continue;
    p[++tot] = i;
    while (b % i == 0) b /= i, num[tot]++;
  }
  if (b != 1) p[++tot] = b, num[tot] = 1;
  for (long long i = 1; i <= tot; i++) {
    t = 1, s = 0;
    while ((double)n / p[i] >= (double)t) t *= p[i], s += n / t;
    ans = min(ans, s / num[i]);
  }
  cout << ans;
  return 0;
}
