#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
char gchar() {
  static char tbuf1[1000], *tmp_st = tbuf1, *tmp_ed = tbuf1;
  if (tmp_st == tmp_ed) {
    int len = fread(tbuf1, 1, 1000, stdin);
    if (len == 0) return -1;
    tmp_ed = tbuf1 + len;
    tmp_st = tbuf1;
  }
  return *(tmp_st++);
}
inline bool gn(int &first) {
  char c, sg = 0;
  while (c = gchar(), (c > '9' || c < '0') && c != '-' && c != -1)
    ;
  if (c == -1) return 0;
  for ((c == '-' ? sg = 1, c = gchar() : 0), first = 0; c >= '0' && c <= '9';
       c = gchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
  return 1;
}
inline bool gn(long long &first) {
  char c, sg = 0;
  while (c = gchar(), (c > '9' || c < '0') && c != '-' && c != -1)
    ;
  if (c == -1) return 0;
  for ((c == '-' ? sg = 1, c = gchar() : 0), first = 0; c >= '0' && c <= '9';
       c = gchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
  return 1;
}
inline bool gn(char &first) {
  while (first = gchar(), first != -1 && isspace(first))
    ;
  return first != -1;
}
inline bool gn(string &s) {
  char c;
  s.clear();
  while (c = gchar(), c != -1 && isspace(c))
    ;
  if (c != -1) s += c;
  while (c = gchar(), c != -1 && !isspace(c)) s += c;
  return c != -1;
}
inline bool gn(double &first) {
  string s;
  bool ok = gn(s);
  first = atof(s.c_str());
  return ok;
}
inline bool gn(char *s) {
  string s1;
  bool ok = gn(s1);
  strcpy(s, s1.c_str());
  return ok;
}
inline bool my_gets(char *s) {
  char c, t = 0;
  while (c = gchar(), c != -1 && c != '\n') *s++ = c, t = 1;
  *s = 0;
  return c != -1 || t;
};
inline void print(int first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
inline void print(long long first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
inline bool print(char &first) { putchar(first); }
inline void print(double &first) { printf("%.10lf", first); }
inline void print(char *s) { printf("%s", s); }
inline void print(string &s) { printf("%s", s.c_str()); }
template <class T, class T1>
inline bool gn(T &first, T1 &second) {
  bool ok = gn(first);
  gn(second);
  return ok;
}
template <class T, class T1, class T2>
inline bool gn(T &first, T1 &second, T2 &z) {
  bool ok = gn(first);
  gn(second);
  gn(z);
  return ok;
}
template <class U, class V, class W, class X>
inline bool gn(U &u, V &v, W &w, X &first) {
  bool ok = gn(u, v);
  gn(w, first);
  return ok;
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
template <class T, class U>
inline void print(T first, U second) {
  printsp(first);
  println(second);
}
template <class T, class U, class V>
inline void print(T first, U second, V z) {
  printsp(first);
  print(second, z);
}
template <class T, class U, class V, class W>
inline void print(T first, U second, V z, W w) {
  printsp(first);
  print(second, z, w);
}
inline int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
const int inf = 0x3f3f3f3f, mod = 1000000007, MOD = 998244353;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double pi = acosl(-1.), eps = 1e-9;
const int NN = 1010101;
int p[NN], flag[NN];
long long get(long long n, long long p) {
  long long r = 1;
  long long ans = 0;
  for (int i = 1;; i++) {
    r *= p;
    ans += n / r;
    if ((double)r * p > 2 * 1e18) break;
  }
  return ans;
}
int main() {
  int cp = 0;
  for (int i = 2; i < NN; i++)
    if (flag[i] == 0) {
      p[cp++] = i;
      for (int j = i + i; j < NN; j += i) flag[j] = 1;
    }
  long long n, B, b;
  gn(n, B);
  b = B;
  vector<pair<long long, int> > v;
  for (int i = 0; i < cp; i++)
    if (b % p[i] == 0) {
      pair<long long, int> r;
      r.first = p[i];
      r.second = 0;
      while (b % p[i] == 0) b /= p[i], r.second++;
      v.push_back(r);
    }
  if (b != 1) v.push_back(pair<long long, int>(b, 1));
  long long ans = INF;
  for (int i = 0; i < v.size(); i++) {
    smin(ans, get(n, v[i].first) / v[i].second);
  }
  println(ans);
  return 0;
}
