#include <bits/stdc++.h>
using namespace std;
void solve() {
  long long n, b;
  cin >> n >> b;
  vector<pair<long long, long long> > ps;
  for (long long i = 2; i * i <= b; ++i) {
    int cnt = 0;
    while (b % i == 0) {
      b /= i;
      ++cnt;
    }
    if (cnt > 0) {
      ps.push_back(make_pair(i, cnt));
    }
  }
  if (b > 1) {
    ps.push_back(make_pair(b, 1));
  }
  long long res = -1;
  for (auto x : ps) {
    long long p = x.first;
    long long c = x.second;
    long long cnt = 0;
    for (long long y = p; y <= n; y *= p) {
      cnt += (n / y);
      if (y > 1 + n / p) break;
    }
    cnt /= c;
    if (res == -1 || cnt < res) res = cnt;
  }
  cout << res << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cout << setprecision(12) << fixed;
  solve();
  return 0;
}
