#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n, b;
  cin >> n >> b;
  vector<pair<long long, long long>> a;
  long long c2 = 0;
  while (b % 2 == 0) {
    b = b / 2;
    c2++;
  }
  if (c2 != 0) {
    a.push_back(pair<long long, long long>(2, c2));
  }
  for (long long i = 3; i <= sqrt(b); i += 2) {
    if (b % i == 0) {
      long long count = 0;
      while (b % i == 0) {
        b = b / i;
        count++;
      }
      a.push_back(pair<long long, long long>(i, count));
    }
    if (b == 1) break;
  }
  if (b != 1) {
    a.push_back(pair<long long, long long>(b, 1));
  }
  long long c[a.size()];
  for (int i = 0; i < a.size(); i++) {
    long long c1 = 0;
    long long x = a[i].first;
    long long p = n;
    while (p >= x) {
      c1 += p / x;
      p = p / x;
    }
    c[i] = c1 / a[i].second;
  }
  long long m = c[0];
  for (int i = 1; i < a.size(); i++) {
    m = min(m, c[i]);
  }
  cout << m << endl;
}
