#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f;
const long long modn = 1000000007;
long long n, b;
int is_prime[1001000];
long long solve(long long i, long long cnt) {
  long long ans = 0;
  long long bb = n;
  while (bb) {
    ans += bb / i;
    bb /= i;
  }
  ans /= cnt;
  return ans;
}
int main() {
  for (int i = 2; i < 1001000; i++) {
    if (is_prime[i] == 0) {
      for (int j = i + i; j < 1001000; j += i) is_prime[j] = 1;
    }
  }
  cin >> n >> b;
  long long ans = 0x3f3f3f3f3f3f3f3fll;
  long long bb = b;
  for (long long i = 2; i * i <= bb; i++) {
    int cnt = 0;
    while (bb % i == 0) {
      cnt++;
      bb /= i;
    }
    if (cnt && (is_prime[i] == 0)) {
      ans = min(ans, solve(i, cnt));
    }
  }
  if (bb != 1) ans = min(ans, solve(bb, 1));
  cout << ans << endl;
  return 0;
}
