#include <iostream>
#include <fstream>

#include <vector>
#include <cmath>

inline long long max_pow(long long& n, long long div) {
  long long sol = 0;
  while (n % div == 0) {
    sol++;
    n /= div;
  }
  return sol;
}

void decompose(long long b,
               std::vector<std::pair<long long, long long> >& pdiv) {
  if (long long p2 = max_pow(b, 2)) {
    pdiv.push_back(std::make_pair(2, p2));
  }

  for (long long i = 3; i <= sqrt(b) + 1; i += 2) {
    if (long long p = max_pow(b, i)) {
      pdiv.push_back(std::make_pair(i, p));
    }
  }

  if (b != 1) {
    pdiv.push_back(std::make_pair(b, 1));
  }
}

inline long long fact_count(long long n, long long pdiv) {
  long long sol = 0;
  long long pdivpow = pdiv;
  while (n / pdivpow) {
    int k = n / pdivpow;
    sol += (1 + n) * k - pdivpow * k * (k + 1) / 2;
    pdivpow *= pdiv;
  }

  return sol;
}

int main()
{
  std::ifstream in("zero2.in");
  std::ofstream out("zero2.out");

  for (long long test = 0; test < 10; ++test) {
    long long n, b;
    in >> n >> b;
    std::vector<std::pair<long long, long long> > pdiv;
    decompose(b, pdiv);

    // And now go in an count.
    std::vector<long long> pn;
    for (long long i = 0; i < pdiv.size(); ++i) {
      pn.push_back(fact_count(n, pdiv[i].first));
    }

    // And now go in an compute the least.
    long long solmin;
    for (long long i = 0; i < pdiv.size(); ++i) {
      if (i == 0 || solmin > pn[i] / pdiv[i].second) {
        solmin = pn[i] / pdiv[i].second;
      }
    }

    out << solmin << std::endl;
  }

  in.close();
  out.close();

  return 0;
}