#include <bits/stdc++.h>
bool x[10000001] = {false};
using namespace std;
unsigned long long int gcd(unsigned long long int a, unsigned long long int b) {
  if (a == 0) {
    return (b);
  } else {
    return (gcd(b % a, a));
  }
}
vector<unsigned long long int> pri;
unsigned long long int fast(unsigned long long int n,
                            unsigned long long int a) {
  if (n == 0)
    return (1);
  else if (n == 1)
    return (a);
  else {
    unsigned long long int r = fast(n / 2, a) % 1000000007;
    if (n % 2 == 0)
      return (((r % 1000000007) * (r % 1000000007)) % 1000000007);
    else
      return (((((r % 1000000007) * a) % 1000000007) * r) % 1000000007);
  }
}
int main() {
  unsigned long long int n, b;
  scanf("%lld%lld", &n, &b);
  unsigned long long int N = n, jj = n;
  vector<pair<unsigned long long int, unsigned long long int> > vec;
  unsigned long long int p = 2, r = 0;
  while (b % 2 == 0) {
    r++;
    b /= 2;
  }
  if (r > 0) {
    vec.push_back(make_pair(2, r));
  }
  for (unsigned long long int i = 3; i * i <= b; i += 2) {
    r = 0;
    while (b % i == 0) {
      b /= i;
      r++;
    }
    if (r > 0) {
      vec.push_back(make_pair(i, r));
    }
  }
  if (b > 1) {
    vec.push_back(make_pair(b, 1));
  }
  vector<unsigned long long int> ans;
  for (unsigned long long int i = 0; i < vec.size(); i++) {
    unsigned long long int S = 0, k = vec[i].first;
    while (N / k > 0) {
      S += N / k;
      N /= k;
    }
    S /= vec[i].second;
    ans.push_back(S);
    N = jj;
  }
  sort(ans.begin(), ans.end());
  printf("%lld", ans[0]);
}
