#include <bits/stdc++.h>
using namespace std;
vector<pair<long long int, long long int> > factors;
long long int count(long long int p, long long int n) {
  long long int cnt = 0;
  while (n > 1) {
    cnt += n / p;
    n /= p;
  }
  return cnt;
}
void prime_factors(long long int b) {
  for (long long int i = 2; i * i <= b; i++) {
    if (b % i == 0) {
      long long int cnt = 0;
      while (b % i == 0) {
        cnt++;
        b /= i;
      }
      factors.emplace_back(i, cnt);
    }
  }
  if (b > 1) factors.emplace_back(b, 1);
}
void solve() {
  long long int n, b;
  cin >> n >> b;
  prime_factors(b);
  long long int ans = 1e18;
  for (auto fact : factors) {
    long long int y = count(fact.first, n);
    ans = min(ans, y / fact.second);
  }
  cout << ans << "\n";
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int test_cases = 1;
  while (test_cases--) {
    solve();
  }
  return 0;
}
