#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
long long n, ba, ans = 2e18;
long long a[maxn], b[maxn];
long long calc(long long t) {
  long long re = 0;
  long long now = t, pre = 1;
  while (now <= n) {
    re += (n / now - n / now / t) * pre;
    if (n / t < now) break;
    now *= t;
    pre++;
  }
  return re;
}
int main() {
  scanf("%lld%lld", &n, &ba);
  long long tmp = ba;
  for (long long i = 2; i <= tmp && i * i <= ba; i++) {
    if (tmp % i != 0) continue;
    a[++a[0]] = i;
    while (tmp % i == 0) tmp /= i, b[a[0]]++;
  }
  if (tmp > 1) a[++a[0]] = tmp, b[a[0]] = 1;
  for (int i = 1; i <= a[0]; i++) ans = min(ans, calc(a[i]) / b[i]);
  printf("%lld", ans);
  return 0;
}
