#include <bits/stdc++.h>
using namespace std;
template <typename T>
T gcd(T a, T b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
vector<long long> b_v;
void bin(unsigned long long n) {
  if (n > 1) bin(n >> 1);
  b_v.emplace_back(n & 1);
}
long long isPowerof2(long long x) { return (x && !(x & x - 1)); }
vector<long long> primefactors(long long n) {
  vector<long long> pf;
  long long maxPrime = -1;
  while (n % 2 == 0) {
    maxPrime = 2;
    pf.emplace_back(2);
    n >>= 1;
  }
  for (long long i = 3; i <= sqrt(n); i += 2) {
    while (n % i == 0) {
      maxPrime = i;
      pf.emplace_back(i);
      n = n / i;
    }
  }
  if (n > 2) maxPrime = n, pf.emplace_back(n);
  return pf;
}
long long powerinfactorial(long long fact, long long p) {
  long long res = 0;
  while (fact > 0) {
    res += fact / p;
    fact /= p;
  }
  return res;
}
long long multiplicity(long long x, long long first) {
  long long res = 0;
  while (x % first == 0) {
    res++;
    x /= first;
  }
  return res;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ostream_iterator<long long> output(cout, " ");
  long long n, b;
  cin >> n >> b;
  vector<long long> v = primefactors(b);
  map<long long, long long> m;
  for (long long(i) = (0); i < (v.size()); i++) {
    m[v[i]]++;
  }
  long long ans = 1e18;
  for (auto itr = m.begin(); itr != m.end(); itr++) {
    long long fac = itr->first;
    long long mul = itr->second;
    long long tmp = powerinfactorial(n, fac) / mul;
    if (tmp < ans) ans = tmp;
  }
  cout << ans;
  return 0;
}
