#include <bits/stdc++.h>
using namespace std;
long long n, b;
long long cal(long long p) {
  long long res = 0, m = n;
  while (m > 0) {
    res += m / p;
    m /= p;
  }
  return res;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> b;
  long long res = 1000000000000000018;
  for (long long p = 2; p * p <= b; ++p)
    if (b % p == 0) {
      long long x = 0;
      while (b % p == 0) {
        ++x;
        b /= p;
      }
      res = min(res, cal(p) / x);
    }
  if (b > 1) res = min(res, cal(b));
  cout << res;
}
