#include <bits/stdc++.h>
#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")
using namespace std;
long long int findPowerOfP(long long int n, long long int p) {
  long long int cnt = 0;
  long long int r = p;
  while (r <= n) {
    cnt += (n / r);
    r = 1LL * r * p;
  }
  return cnt;
}
vector<pair<long long int, long long int> > primeFactorsofK(long long int k) {
  vector<pair<long long int, long long int> > ans;
  for (long long int i = 2; k != 1; i++) {
    if (k % i == 0) {
      long long int count = 0;
      while (k % i == 0) {
        k = k / i;
        count++;
      }
      ans.push_back(make_pair(i, count));
    }
  }
  return ans;
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  long long int n, b;
  cin >> n >> b;
  long long int ans = 1000000000000000000LL;
  for (long long int i = 2; i <= b; i++) {
    if (1LL * i * i > b) i = b;
    long long int cnt = 0;
    while (b % i == 0) {
      b /= i;
      cnt++;
    }
    if (cnt == 0) continue;
    long long int x = 0, m = 1;
    while (m <= n / i) {
      m *= i;
      x += n / m;
    }
    ans = min(ans, x / cnt);
  }
  cout << ans << '\n';
  return 0;
}
