#include <bits/stdc++.h>
using namespace std;
long long prime[1000005];
struct node {
  long long num;
  long long data;
} a[1000005];
;
bool vis[10000005];
long long b;
long long init() {
  memset(vis, false, sizeof(vis));
  long long k = 0, i;
  for (i = 2; i <= 10000000; i++) {
    if (!vis[i]) {
      prime[k++] = i;
      for (long long j = 2; i * j <= 10000000; j++) vis[i * j] = true;
    }
  }
  return k;
}
int main() {
  long long k, i, j, n, cnt, sum, t = 78498, r, mini;
  t = init();
  while (scanf("%I64d%I64d", &n, &b) != EOF) {
    cnt = 0;
    sum = 0;
    r = b;
    for (i = 0; i < t && b != 1; i++) {
      if (b % prime[i] == 0) {
        a[cnt].data = prime[i];
        a[cnt].num = 0;
        while (b % prime[i] == 0) {
          a[cnt].num++;
          b /= prime[i];
        }
        cnt++;
      }
    }
    if (b != 1) a[cnt].data = b, a[cnt++].num = 1;
    b = r;
    for (i = 0; i < cnt; i++) {
      for (j = a[i].data, sum = 0, r = 1; j <= n; j *= a[i].data) {
        sum += (n / j);
        if (n / j < a[i].data) break;
      }
      if (i == 0)
        mini = sum / a[i].num;
      else
        mini = min(mini, sum / a[i].num);
    }
    printf("%I64d\n", mini);
  }
}
