#include <bits/stdc++.h>
using namespace std;
struct pf {
  long long pr;
  long long ct;
};
bitset<1000001> pr;
vector<int> prs;
int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL);
  long long n, b;
  cin >> n >> b;
  for (int i = 2; i < 1000001; i++) {
    if (pr[i] == 0) {
      for (int j = 2 * i; j <= 1000000; j += i) {
        pr[j] = 1;
      }
    }
  }
  for (int i = 2; i < 1000001; i++) {
    if (pr[i] == 0) prs.push_back(i);
  }
  vector<struct pf> prime_f;
  long long tm = b;
  int j = 0;
  while (tm > 1 and j < prs.size()) {
    if (tm % prs[j] == 0) {
      int ct = 0;
      while (tm % prs[j] == 0 and tm > 1) {
        tm /= prs[j];
        ct++;
      }
      struct pf tt = {prs[j], ct};
      prime_f.push_back(tt);
    }
    j++;
  }
  if (tm > 1) {
    struct pf tt = {tm, 1};
    prime_f.push_back(tt);
  }
  long long cnt[prime_f.size()];
  memset(cnt, 0, sizeof(cnt));
  long long sq = sqrt((double)n);
  for (int i = 0; i < prime_f.size(); i++) {
    long long pw = prime_f[i].pr;
    long long lg = (long long)(log(n) / log(prime_f[i].pr));
    long long pp = 1;
    while (pp <= lg) {
      cnt[i] += (long long)(n / pw);
      pw *= prime_f[i].pr;
      pp++;
    }
  }
  long long mn = (long long)(1e18);
  for (int i = 0; i < prime_f.size(); i++) {
    cnt[i] = cnt[i] / prime_f[i].ct;
    mn = ((cnt[i] < mn) ? cnt[i] : mn);
  }
  cout << mn << endl;
  return 0;
}
