#include<bits/stdc++.h>

using namespace std;

ifstream fin ("zero2.in");
ofstream fout ("zero2.out");

long long n, b;

int main()
{
  for (int tt = 1; tt <= 10; tt++) {
    fin >> n >> b;
    vector<pair<int, int> >prim;
    for (int j = 2; j  * j <= b;j++) {
      int e = 0;
      while (b % j == 0) {
        e++;
        b /= j;
      }
      if (e) {
        prim.push_back({j, e});
      }
    }
    if (b > 1)
      prim.push_back({b, 1});
    long long t = LLONG_MAX;
    for (auto it : prim) {
      long long pw = it.first;
      long long exp = 0;
      while (pw <= n) {
        long long nr = n / pw;
        exp += 1ll * pw * nr * (nr - 1) / 2 + (n - nr * pw + 1) * nr;
        pw *= it.first;
      }
      t = min(t, exp / it.second);
    }
    fout << t << "\n";
  }
  return 0;
}