#include <bits/stdc++.h>
using namespace std;
long long n, b;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> b;
  long long Min = 1e18;
  for (long long i = 2; i * i <= b; i++)
    if (b % i == 0) {
      long long k = 0;
      while (b % i == 0) {
        b /= i;
        k++;
      }
      long long x = i;
      long long y = 0;
      while (x <= n) {
        y += n / x;
        if (x > 2e18 / i)
          x = 2e18;
        else
          x *= i;
      }
      Min = min(Min, y / k);
    }
  if (b > 1) {
    long long i = b;
    long long k = 0;
    while (b % i == 0) {
      b /= i;
      k++;
    }
    long long x = i;
    long long y = 0;
    while (x <= n) {
      y += n / x;
      if (x > 2e18 / i)
        x = 2e18;
      else
        x *= i;
    }
    Min = min(Min, y / k);
  }
  cout << Min;
}
