#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
const int maxm = 2e5 + 10;
vector<long long> tmp;
int cnt[maxn];
long long solve(long long first, long long second) {
  long long sum = 0;
  while (first) {
    sum += first / second;
    first /= second;
  }
  return sum;
}
int main() {
  long long a, b;
  cin >> a >> b;
  int tot = 0;
  for (long long i = 2; i * i <= b; ++i)
    if (b % i == 0) {
      tmp.push_back(i);
      while (b % i == 0) {
        b /= i;
        ++cnt[tot];
      }
      ++tot;
    }
  if (b > 1) {
    tmp.push_back(b);
    ++cnt[tot];
    ++tot;
  }
  long long ans = LLONG_MAX;
  for (int i = 0; i < tot; ++i) ans = min(ans, solve(a, tmp[i]) / cnt[i]);
  cout << ans << '\n';
  return 0;
}
