#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
const int N = 1e5 + 5;
const int inf = 1e9;
const long long INF = 1e18;
const double PI = acos(-1.0);
const double EPS = 1e-8;
const int MOD = 1000000007;
long long int n, b;
struct PRIME_FACTORIZE_POLLARD_RHO {
  const long double range = 1e18;
  inline long long int MulMod(long long int a, long long int b,
                              long long int c) {
    long long int x = 0, y = a % c;
    while (b > 0) {
      if (b & 1) x = (x + y) % c;
      y = (y << 1) % c;
      b = b >> 1;
    }
    return x;
  }
  inline long long int Modulo(long long int a, long long int b,
                              long long int c) {
    long long int x = 1, y = a % c;
    while (b > 0) {
      if (b & 1) x = MulMod(x, y, c);
      y = MulMod(y, y, c);
      b = b >> 1;
    }
    return x;
  }
  inline bool Miller(long long int p, int iter) {
    if (p < 2) return false;
    if (p == 2) return true;
    if (!(p & 1)) return false;
    long long int s = p - 1, a, temp, mod;
    while (!(s & 1)) s = s >> 1;
    for (int i = 0; i < iter; i++) {
      a = rand() % (p - 1) + 1;
      temp = s;
      mod = Modulo(a, temp, p);
      while (temp != (p - 1) && mod != 1 && mod != (p - 1)) {
        mod = MulMod(mod, mod, p);
        temp = temp << 1;
      }
      if (mod != (p - 1) && !(temp & 1)) return false;
    }
    return true;
  }
  inline long long int Randerson() {
    long double pseudo = (long double)rand() / (long double)RAND_MAX;
    return (long long)(round((long double)range * pseudo)) + 1;
  }
  inline long long int Calc(long long int x, long long int n, long long int c) {
    return (MulMod(x, x, n) + c) % n;
  }
  inline long long int GCD(long long int a, long long int b) {
    return !b ? a : GCD(b, a % b);
  }
  inline long long int Pollard_Rho(long long int n) {
    long long int d = 1, i = 1, k = 1, x = 2, y = x, c;
    do {
      c = Randerson() % n;
    } while ((c == 0) || (c + 2) % n == 0);
    while (d != n) {
      if (i == k) k *= 2LL, y = x, i = 0;
      x = Calc(x, n, c);
      i++;
      d = GCD(abs(y - x), n);
      if (d != 1) return d;
    }
  }
  inline vector<long long int> GetPrimeFactors(long long int n) {
    vector<long long int> ret;
    if (n == 1) return ret;
    if (Miller(n, 5)) {
      ret.push_back(n);
      return ret;
    }
    long long int d = Pollard_Rho(n);
    ret = GetPrimeFactors(d);
    vector<long long int> temp = GetPrimeFactors(n / d);
    for (int i = 0; i < temp.size(); i++) ret.push_back(temp[i]);
    return ret;
  }
} rho;
int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> b;
  vector<long long int> p = rho.GetPrimeFactors(b);
  map<long long int, long long int> M;
  for (auto x : p) M[x]++;
  sort(p.begin(), p.end()), p.erase(unique(p.begin(), p.end()), p.end());
  long long int ans = INF;
  for (auto x : p) {
    long long int cur = x;
    long long int tot = 0;
    while (n / cur) {
      tot += n / cur;
      if (n / x >= cur)
        cur *= x;
      else
        break;
    }
    ans = min(ans, tot / M[x]);
  }
  if (ans == INF)
    cout << 0 << "\n";
  else
    cout << ans << "\n";
  return 0;
}
