#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9 + 7;
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
void div(long long n, vector<long long>& d) {
  for (long long i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      if (n / i == i)
        d.push_back(i);
      else {
        d.push_back(n / i);
        d.push_back(i);
      }
    }
  }
}
int main() {
  long long n, b;
  cin >> n >> b;
  vector<long long> d;
  div(b, d);
  sort(d.begin(), d.end());
  long long x = d.size();
  long long ans = 1e18;
  for (long long i = 1; i < x; ++i) {
    if (isPrime(d[i])) {
      long long temp = b;
      long long pc = 0;
      while (temp % d[i] == 0) {
        pc++;
        temp = temp / d[i];
      }
      long long val = 0;
      long long temp1 = n;
      while (temp1 != 0) {
        temp1 = temp1 / d[i];
        val += temp1;
      }
      val = val / pc;
      ans = min(ans, val);
    }
  }
  cout << ans;
}
