#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, b, s = 0x3f3f3f3f3f3f3f3fLL;
ll f(ll i) {
  ll r = 0, p = 0, m = n;
  while (b % i == 0) b /= i, p++;
  while (m / i > 0) r += m /= i;
  return r / p;
}
int main() {
  scanf("%lld%lld", &n, &b);
  for (ll i = 2; i * i <= b; i++)
    if (b % i == 0) s = min(s, f(i));
  if (b > 1) s = min(s, f(b));
  printf("%lld", s);
}
