#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double pii = 2 * pi;
const double eps = 1e-6;
const double inf = 1e15;
map<long long int, long long int> m;
void primeFactors(long long int n) {
  while (n % 2 == 0) {
    m[2]++;
    n = n / 2;
  }
  for (long long int i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      m[i]++;
      n = n / i;
    }
  }
  if (n > 2) m[n]++;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int n, b;
  cin >> n >> b;
  primeFactors(b);
  long long int ans = n;
  for (auto i : m) {
    long long int N = n;
    long long int s = 0;
    long long int r = i.first;
    while (N / r > 0) {
      s += (N / r);
      N /= r;
    }
    s = (s / i.second);
    ans = min(ans, s);
  }
  cout << ans << "\n";
  cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
  return 0;
}
