#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
bool mark[N];
vector<int> prime;
void seive() {
  prime.push_back(2);
  int sq = sqrt(N), i, j;
  for (i = 3; i < N; i += 2) mark[i] = true;
  for (i = 3; i <= sq; i += 2)
    if (mark[i])
      for (j = i * i; j < N; j += i) mark[j] = true;
  for (i = 3; i < N; i += 2)
    if (mark[i]) prime.push_back(i);
}
vector<pair<long long int, long long int> > fact;
void Fact(long long int x) {
  int i, j, k, ct, sq = sqrt(x);
  for (i = 0; i < prime.size() && prime[i] <= sq; i++) {
    ct = 0;
    if (x % prime[i] == 0) {
      while (x % prime[i] == 0) {
        x /= prime[i], ++ct;
      }
      if (ct > 0) fact.push_back(make_pair(prime[i], ct));
      sq = sqrt(x);
    }
    if (x < prime[i]) break;
  }
  if (x > 1) fact.push_back(make_pair(x, 1));
}
long long int nai(long long int n, long long int x, long long int pr) {
  long long int ct = 0, p, q, xp = x;
  while (xp <= n) {
    ct += (n / xp);
    if (xp > (n / x)) break;
    xp *= x;
  }
  return ct / pr;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int a, b, c, i, j, k, q, p, x, y, sum, ct, ct1, m, mid, l, r, len,
      x1, y1, mn, n;
  char ch;
  double d;
  string str1, str2;
  bool bl, bl1;
  seive();
  while (cin >> n >> b) {
    fact.clear();
    Fact(b);
    long long int tl = 1e18 + 200;
    for (auto xx : fact) {
      tl = min(tl, (nai(n, xx.first, xx.second)));
    }
    printf("%lld\n", tl);
  }
}
