#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const int MAXN = 1000000 + 5;
const int MAXM = 1000000 + 5;
long long factor[100][2];
int cnt;
void getFactors(long long n) {
  cnt = 0;
  for (int i = 2; i <= n / i; i++) {
    if (n % i == 0) {
      factor[cnt][0] = i;
      factor[cnt][1] = 0;
      while (n % i == 0) {
        factor[cnt][1]++;
        n /= i;
      }
      cnt++;
    }
  }
  if (n != 1) {
    factor[cnt][0] = n;
    factor[cnt][1] = 1;
    cnt++;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, b;
  cin >> n >> b;
  getFactors(b);
  long long ans = 0x3f3f3f3f3f3f3f3fLL;
  for (int i = 0; i < cnt; i++) {
    long long p = factor[i][0];
    long long r = factor[i][1];
    long long tmp = 0;
    long long _p = p;
    while (p <= n) {
      tmp += n / p;
      if (p > n / _p) {
        break;
      }
      p *= _p;
    }
    ans = min(ans, tmp / r);
  }
  cout << ans << endl;
  return 0;
}
