#include <bits/stdc++.h>
using namespace std;
const long long int N = 200009;
long long int n, k;
long long int Calc(long long int k) {
  long long int m = k, kq = 0;
  while (true) {
    kq += n / m;
    if (n / k < m) {
      break;
    }
    m = m * k;
  }
  return kq;
}
vector<pair<long long int, long long int> > p;
const long long int S = 1e6;
void Pre() {
  cin >> n >> k;
  long long int nk = k;
  for (int i = 2; i <= S; i++) {
    if (nk % i == 0) {
      long long int cnt = 0;
      while (nk % i == 0) {
        nk /= i;
        cnt++;
      }
      p.push_back(make_pair(i, cnt));
    }
  }
  if (nk != 1) {
    p.push_back(make_pair(nk, 1));
  }
}
void Solve() {
  long long int kq = 1e18;
  for (auto i : p) {
    kq = min(kq, Calc(i.first) / i.second);
  }
  cout << kq;
}
int main() {
  Pre();
  Solve();
}
