#include <bits/stdc++.h>
using namespace std;
long long n, b;
signed main() {
  cin >> n >> b;
  long long ans = 1e18;
  for (long long i = 2; i * i <= b; i++) {
    if (b % i == 0) {
      long long nb = 0;
      while (b % i == 0) {
        b /= i;
        nb++;
      }
      long long num = 0;
      for (long long j = i; j <= n; j *= i) {
        num += n / j;
        if (n / j < i) break;
      }
      ans = min(ans, num / nb);
    }
  }
  if (b > 1) {
    long long num = 0;
    for (long long i = b; i <= n; i *= b) {
      num += n / i;
      if (n / i < b) break;
    }
    ans = min(ans, num);
  }
  printf("%lld", ans);
  return 0;
}
