#include <bits/stdc++.h>
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
bool ck() {
  int x, y, z;
  int a, b, c;
  std::cin >> x >> y >> z;
  std::cin >> a >> b >> c;
  if (x > a) {
    return false;
  }
  int s = a;
  s -= x;
  if (y > s + b) {
    return false;
  }
  s += b;
  s -= y;
  if (z > s + c) {
    return false;
  }
  return true;
}
int64_t cnt(int64_t n, int64_t x) {
  if (n < x) {
    return 0;
  }
  return n / x + cnt(n / x, x);
}
int main() {
  std::ios_base::sync_with_stdio(false);
  int64_t n, m;
  std::cin >> n >> m;
  std::vector<std::pair<int64_t, int>> primes;
  auto tmp = m;
  for (int64_t fac = 2; fac * fac <= tmp; ++fac) {
    if (tmp % fac == 0) {
      primes.emplace_back(fac, 0);
      while (tmp % fac == 0) {
        ++primes.back().second;
        tmp /= fac;
      }
    }
  }
  if (tmp > 1) {
    primes.emplace_back(tmp, 1);
  }
  std::vector<int64_t> a;
  for (const auto &p : primes) {
    auto x = p.first;
    auto y = p.second;
    a.push_back(cnt(n, x) / y);
  }
  int64_t ans = 0;
  if (!a.empty()) {
    ans = *std::min_element(a.begin(), a.end());
  }
  std::cout << ans << std::endl;
}
