#include <bits/stdc++.h>
using namespace std;
const int DN = 2e5 + 5;
long long n, b, f, cnt, nr, r[DN], mi = 1e18;
void solve(long long f, long long g) {
  long long put = f, z = 1, sol = 0;
  while (1) {
    sol += n / put;
    z++;
    if (put > n / f) break;
    put *= f;
  }
  sol /= g;
  mi = min(mi, sol);
}
int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  cin >> n >> b;
  f = b;
  for (long long d = 2; d * d <= f; d++)
    if (f % d == 0) {
      cnt = 0;
      while (f % d == 0) {
        cnt++;
        f /= d;
      }
      solve(d, cnt);
    }
  if (f != 1) solve(f, 1);
  cout << mi;
}
