#include <bits/stdc++.h>
using namespace std;
long long cnt = 0;
long long num[4000005];
void primeFactor(long long n) {
  while (n % 2 == 0) {
    num[cnt++] = 2;
    n /= 2;
  }
  for (long long i = 3; i <= sqrt(n); i += 2) {
    while (n % i == 0) {
      num[cnt++] = i;
      n /= i;
    }
  }
  if (n > 2) num[cnt++] = n;
}
int main() {
  long long n, b;
  scanf("%lld%lld", &n, &b);
  primeFactor(b);
  long long s, ss, sss, ans;
  long long k = 1;
  long long minn = 4e18;
  for (long long t = 0; t < cnt; t++) {
    if (num[t] != num[t + 1]) {
      s = 0;
      ans = n;
      ss = num[t];
      while (ans >= ss) {
        s += (ans / ss);
        ans /= ss;
      }
      minn = min(minn, s / k);
      k = 1;
    } else
      k++;
  }
  printf("%lld", minn);
  return 0;
}
