#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n, b;
  cin >> n >> b;
  map<long long, long long> res;
  for (long long i = 2; i * i <= b; i++) {
    while (b % i == 0) {
      res[i]++;
      b /= i;
    }
  }
  if (b != 1) {
    res[b]++;
  }
  long long mi = 9223372036854775807;
  for (auto p : res) {
    long long t = p.first;
    long long cnt = 0, X = n;
    while (X) {
      cnt += X / t;
      X /= t;
    }
    mi = min(mi, cnt / p.second);
  }
  cout << mi << endl;
}
