#include <bits/stdc++.h>
using namespace std;
long long fal(long long fact, long long p) {
  long long rep = 0;
  while (fact > 0) {
    rep += (fact / p);
    fact /= p;
  }
  return rep;
}
long long cal(long long fact, long long n) {
  long long rep = 1000000000000000000, z = sqrt(n);
  for (long long i = 2; i <= z; i++) {
    long long cnt = 0;
    while (n % i == 0) {
      cnt++;
      n = n / i;
    }
    if (cnt > 0) {
      long long pep = fal(fact, i) / cnt;
      rep = min(rep, pep);
    }
  }
  if (n >= 2) {
    long long pep = fal(fact, n);
    rep = min(rep, pep);
  }
  return rep;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0);
  long long n, b;
  cin >> n >> b;
  long long x = cal(n, b);
  cout << x;
  return 0;
}
