#include <bits/stdc++.h>
using namespace std;
int main() {
  long long int n, b, result = 1e19;
  scanf("%lld %lld", &n, &b);
  for (long long int i = 2; i < b + 1; i++) {
    if (b < i * i) {
      i = b;
    }
    int numOfDigits = 0;
    while (!(b % i)) {
      b = b / i;
      numOfDigits = numOfDigits + 1;
    }
    if (numOfDigits != 0) {
      long long int x = 1, y = 0;
      while (n / i >= x) {
        x = i * x;
        y = n / x + y;
      }
      if (y / numOfDigits < result) {
        result = y / numOfDigits;
      }
    }
  }
  printf("%lld", result);
  return 0;
}
