#include <bits/stdc++.h>
using namespace std;
const unsigned long long MAXN = 1000010;
vector<unsigned long long> primes;
bitset<1000100> is_prime;
void sieve() {
  is_prime.set();
  is_prime[0] = is_prime[1] = 0;
  for (unsigned long long i = 2; i < MAXN; i++) {
    if (is_prime[i]) {
      primes.push_back(i);
      for (unsigned long long j = i * i; j < MAXN; j += i) is_prime[j] = 0;
    }
  }
}
vector<pair<unsigned long long, unsigned long long> > getfactors(
    unsigned long long n) {
  sieve();
  vector<pair<unsigned long long, unsigned long long> > ans;
  for (unsigned long long i = 0; i < primes.size(); i++) {
    if (n % primes[i] == 0) {
      ans.push_back({primes[i], 0});
      while (n % primes[i] == 0) {
        ans.back().second++;
        n /= primes[i];
      }
    }
  }
  if (n > 1) ans.push_back({n, 1});
  return ans;
}
int main() {
  unsigned long long n, b;
  scanf("%llu %llu", &n, &b);
  vector<pair<unsigned long long, unsigned long long> > fact = getfactors(b);
  unsigned long long ans = numeric_limits<unsigned long long>::max();
  for (auto f : fact) {
    unsigned long long aux = 0;
    unsigned long long a = n;
    while (a / f.first) {
      aux += a / f.first;
      a /= f.first;
    }
    aux /= f.second;
    ans = min(ans, aux);
  }
  assert(ans != numeric_limits<unsigned long long>::max());
  printf("%llu\n", ans);
  return 0;
}
