#include <bits/stdc++.h>
using namespace std;
vector<long long> vec;
vector<long long> t;
const int max_n = 1000010;
bool is_prime[max_n];
long long b;
void test(long long i) {
  long long ans = 0;
  if (i == 1) return;
  while (b % i == 0) {
    ans++;
    b /= i;
  }
  if (ans >= 1) {
    vec.push_back(i);
    t.push_back(ans);
  }
}
vector<long long> primes;
void fact() {
  for (int i = 0; i < primes.size(); i++) {
    if (b % primes[i] == 0) {
      test(primes[i]);
    }
  }
}
int main() {
  for (int i = 1; i < max_n; i++) is_prime[i] = true;
  for (int i = 2; i < max_n; i++) {
    if (is_prime[i]) primes.push_back(i);
    for (int j = i + i; j < max_n; j += i) is_prime[j] = false;
  }
  long long n;
  cin >> n >> b;
  fact();
  if (b != 1) {
    vec.push_back(b);
    t.push_back(1);
  }
  long long ans = 1e18;
  for (int i = 0; i < vec.size(); i++) {
    long long tmp = vec[i];
    long long cnt = 0;
    long long nn = n;
    while (tmp <= nn) {
      cnt += nn / tmp;
      nn /= tmp;
    }
    ans = min(ans, cnt / t[i]);
  }
  cout << ans << endl;
  return 0;
}
