#include <bits/stdc++.h>
using namespace std;
long long n, b, ans;
vector<long long> apar;
vector<pair<long long, int>> fact;
long long add(long long x) {
  long long rez = 0;
  for (long long y = x; y <= n;) {
    rez += n / y;
    if (y > n / x) break;
    y *= x;
  }
  return rez;
}
int main() {
  cin >> n >> b;
  for (long long d = 2; d * d <= b; ++d) {
    if (b % d == 0) {
      fact.emplace_back(d, 0);
      while (b % d == 0) b /= d, fact.back().second++;
    }
  }
  if (b > 1) fact.emplace_back(b, 1);
  long long minElem = 1e18;
  for (int i = 0; i < fact.size(); ++i) {
    minElem = min(minElem, add(fact[i].first) / fact[i].second);
  }
  cout << minElem;
}
