#include <bits/stdc++.h>
using namespace std;
long long factorize_factorial(long long n, long long a) {
  long long x = 1;
  long long count = 0;
  while (1) {
    if (n / ((long long)pow(a, x)) == 0) {
      break;
    } else {
      long long y = pow(a, x);
      count += n / y;
      x++;
    }
  }
  return count;
}
void factorize(unordered_map<long long, long long>& mp, long long n) {
  int count = 0;
  while (!(n % 2)) {
    n >>= 1;
    count++;
  }
  if (count) mp[2] = count;
  for (long long i = 3; i <= sqrt(n); i += 2) {
    count = 0;
    while (n % i == 0) {
      count++;
      n = n / i;
    }
    if (count) mp[i] = count;
  }
  if (n > 2) mp[n] = 1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long n, b;
  cin >> n >> b;
  unordered_map<long long, long long> mp;
  mp.clear();
  unordered_map<long long, long long> mp_1;
  mp_1.clear();
  factorize(mp_1, b);
  long long min_no = 1e18;
  unordered_map<long long, long long>::iterator itr;
  for (itr = mp_1.begin(); itr != mp_1.end(); ++itr) {
    mp[itr->first] = factorize_factorial(n, itr->first);
    long long a = mp[itr->first];
    min_no = min(min_no, a / itr->second);
  }
  cout << min_no;
  return 0;
}
