#include <bits/stdc++.h>
using namespace std;
map<unsigned long long, unsigned long long> m;
unsigned long long nn;
void primeFactors(unsigned long long n) {
  while (n % 2 == 0) {
    m[2]++;
    n = n / 2;
  }
  for (unsigned long long i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      m[i]++;
      n = n / i;
    }
  }
  if (n > 2) m[n]++;
}
unsigned long long fnc(unsigned long long prime, unsigned long long power) {
  unsigned long long sum = 0;
  unsigned long long d = prime;
  while (1) {
    sum += nn / d;
    if (d > (nn / prime) || d > 1e18) break;
    d *= prime;
  }
  return (sum / power);
}
void solve() {
  unsigned long long k;
  cin >> nn >> k;
  primeFactors(k);
  unsigned long long cnt = 0;
  unsigned long long ans = 3000000000000000000;
  for (auto it : m) {
    unsigned long long prime = it.first;
    unsigned long long power = it.second;
    ans = min(ans, fnc(prime, power));
  }
  cout << ans << '\n';
}
signed main() {
  unsigned long long t;
  t = 1;
  while (t--) solve();
  return 0;
}
