#include <bits/stdc++.h>
using namespace std;
long long cal(long long x, long long a) {
  long long y = a, ans = 0, cnt = 1;
  while (x / (long long)(pow(a, cnt)) != 0) {
    ans += x / (long long)(pow(a, cnt));
    cnt++;
  }
  return ans;
}
signed main() {
  long long n, b, mx = LLONG_MAX;
  vector<long long> v, k;
  cin >> n >> b;
  for (long long i = 2; i * i <= b; i++) {
    if (b % i == 0) {
      long long cnt = 0;
      v.push_back(i);
      while (b % i == 0) {
        b = b / i;
        cnt++;
      }
      k.push_back(cnt);
    }
  }
  if (b != 1) v.push_back(b), k.push_back(1);
  for (long long i = 0; i < v.size(); i++) {
    mx = min(cal(n, v[i]) / k[i], mx);
  }
  cout << mx;
}
