#include <bits/stdc++.h>
using namespace std;
long long n, m, u[10010], sl[10010];
int cnt = 0;
int main() {
  scanf("%lld%lld", &n, &m);
  for (int i = 2, l = sqrt(m); i <= l; ++i)
    if (m % i == 0) {
      u[++cnt] = i;
      sl[cnt] = 0;
      while (m % i == 0) {
        ++sl[cnt];
        m /= i;
      }
    }
  if (m != 1) {
    u[++cnt] = m;
    sl[cnt] = 1;
  }
  long long ans = n;
  for (int i = 1; i <= cnt; ++i) {
    long long sum = 0;
    long long j = u[i];
    for (; n / j >= u[i]; j *= u[i]) sum += n / j;
    sum += n / j;
    ans = min(ans, sum / sl[i]);
  }
  printf("%lld", ans);
  return 0;
}
