#include <bits/stdc++.h>
using namespace std;
vector<int> prime;
void sieve() {
  int n = 1e6 + 1;
  vector<bool> mark(n, false);
  prime.push_back(2);
  for (int p = 3; p * p <= n; p = p + 2) {
    if (mark[p] == false) {
      for (int i = p * p; i < n; i += p * 2) {
        mark[i] = true;
      }
    }
  }
  for (int i = 3; i < n; i = i + 2) {
    if (!mark[i]) {
      prime.push_back(i);
    }
  }
}
void solve() {
  long long n, b;
  cin >> n >> b;
  int l = prime.size();
  vector<pair<long long, long long> > v;
  long long x = b;
  for (int i = 0; i < l; i++) {
    long long cnt = 0;
    while ((i < l) && (x > 1)) {
      if ((x % prime[i]) == 0) {
        x /= prime[i];
        cnt++;
        continue;
      }
      break;
    }
    if (cnt != 0) {
      v.push_back(make_pair(prime[i], cnt));
    }
  }
  if (x != 1) {
    v.push_back(make_pair(x, 1));
  }
  long long mn = n;
  for (int i = 0; i < v.size(); i++) {
    long long x = n;
    long long cnt = 0;
    while (x > 0) {
      cnt += (x / (v[i].first));
      x /= v[i].first;
    }
    mn = min(mn, (cnt / (v[i].second)));
  }
  cout << mn << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  sieve();
  int test_case = 1;
  while (test_case-- > 0) {
    solve();
  }
  return 0;
}
