#include <bits/stdc++.h>
using namespace std;
vector<int> primes;
vector<pair<unsigned long long int, unsigned long long int>> factors;
bool prime[1000001];
bool comp(pair<int, int> a, pair<int, int> b) { return (a.first < b.first); }
void sieve() {
  prime[0] = prime[1] = false;
  for (int i = 2; i * i <= 1000000; i++) {
    if (prime[i]) {
      for (int j = 2 * i; j <= 1000000; j += i) prime[j] = false;
    }
  }
  for (int i = 0; i <= 1000000; i++) {
    if (prime[i]) primes.push_back(i);
  }
}
void factorize(unsigned long long int n) {
  unsigned long long int chk1 = n;
  unsigned long long int count = 0;
  while (!(n % 2)) {
    n >>= 1;
    count++;
  }
  if (count) factors.push_back(make_pair(2, count));
  for (long long i = 3; i <= sqrt(n); i += 2) {
    count = 0;
    while (n % i == 0) {
      count++;
      n = n / i;
    }
    if (count) factors.push_back(make_pair(i, count));
  }
  count = 0;
  if (n > 2) {
    factors.push_back(make_pair(n, 1));
  }
}
int main() {
  memset(prime, true, sizeof(prime));
  sieve();
  unsigned long long int n, b;
  cin >> n >> b;
  unsigned long long int ans = 10000000000000000000;
  unsigned long long int chk = n;
  factorize(b);
  sort(factors.begin(), factors.end(), comp);
  for (int i = 0; i < factors.size(); i++) {
    chk = n;
    unsigned long long int ans1 = 0;
    unsigned long long int take = factors[i].first;
    while (n / take > 0) {
      ans1 += n / take;
      n /= take;
    }
    n = chk;
    ans = min(ans, ans1 / factors[i].second);
  }
  cout << ans;
}
