#include <bits/stdc++.h>
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  std::cerr.tie(0);
  long long n, b;
  while (std::cin >> n >> b) {
    std::vector<long long> prime, count;
    for (long long i = 2; i * i <= b; ++i) {
      if (b % i == 0) {
        prime.push_back(i);
        count.push_back(1);
        b /= i;
        while (b % i == 0) {
          count.back()++;
          b /= i;
        }
      }
    }
    if (b > 1) {
      prime.push_back(b);
      count.push_back(1);
    }
    long long min = (long long)1e18L;
    for (int id = 0; id < (int)prime.size(); ++id) {
      long long p = prime[id];
      long long cnt = n / p;
      while (p <= n / prime[id]) {
        p *= prime[id];
        cnt += n / p;
      }
      min = std::min(min, cnt / count[id]);
    }
    std::cout << min << "\n";
  }
  return 0;
}
