#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, int>> v;
void zml(long long b) {
  for (long long i = 2; i * i <= b; i++)
    if (b % i == 0) {
      int cnt = 0;
      while (b % i == 0) {
        b /= i;
        cnt++;
      }
      v.push_back({i, cnt});
    }
  if (b != 1) {
    v.push_back({b, 1});
  }
}
int main() {
  long long n, b, ans = 1e18;
  cin >> n >> b;
  zml(b);
  for (auto &z : v) {
    long long ret = 0;
    for (long long i = z.first; i <= n; i *= z.first) {
      ret += n / i;
      if ((long double)i * z.first > n + 1) break;
    }
    ans = min(ans, ret / z.second);
  }
  cout << ans << endl;
}
