#include <bits/stdc++.h>
using namespace std;
const long long N = 50155;
long long n, b, ans = 1e18, c;
vector<long long> x, y;
long long D(long long a) {
  long long felan = 0, aa = a;
  while (1) {
    felan += (n / a);
    if (a > n / aa) break;
    a *= aa;
  }
  return felan;
}
int main() {
  cin >> n >> b;
  for (long long i = 2; i <= sqrt(b); i++) {
    if (b % i == 0) {
      long long now = 0;
      while (b % i == 0) b /= i, now++;
      x.push_back(i);
      y.push_back(now);
    }
  }
  if (b > 1) x.push_back(b), y.push_back(1);
  for (int i = 0; i < x.size(); i++) {
    long long now = x[i];
    long long k = D(now);
    ans = min(ans, k / y[i]);
  }
  cout << ans;
}
