#include <bits/stdc++.h>
using namespace std;
map<long long, long long> mp;
map<long long, long long>::iterator it;
void primeFactors(long long n) {
  while (n % 2 == 0) {
    mp[2]++;
    n = n / 2;
  }
  for (long long i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      mp[i]++;
      n = n / i;
    }
  }
  if (n > 2) {
    mp[n]++;
  }
}
int main() {
  long long n, b;
  cin >> n >> b;
  primeFactors(b);
  long long final_ans = 9223372036854775807;
  for (it = mp.begin(); it != mp.end(); it++) {
    long long a = it->first;
    long long occ = it->second;
    long long i = 1;
    long long sum = 0;
    while (pow(a, i) <= n) {
      sum += (n / pow(a, i));
      i++;
    }
    sum = sum / occ;
    final_ans = min(final_ans, sum);
  }
  cout << final_ans << endl;
  return 0;
}
