#include <bits/stdc++.h>
#define int long long
const int VMAX = 31622;
using namespace std;
ifstream fin ("zero2.in");
ofstream fout ("zero2.out");
bitset<VMAX + 5>ciur;
vector<int>pr;
void sieve(){
    ciur[0] = ciur[1] = 1;
    for (int i = 4; i <= VMAX; i += 2)
        ciur[i] = 1;
    for (int i = 3; i * i <= VMAX; i += 2){
        if (ciur[i] == 0){
            for (int j = i * i; j <= VMAX; j += 2 * i)
                ciur[j] = 1;
        }
    }
    pr.push_back(2);
    for (int i = 3; i <= VMAX; i += 2)
        if (ciur[i] == 0)
            pr.push_back(i);
}
int countt(int n, int p) {
    int put = 0;
    for (int morb = p; p <= n; p *= morb) {
        int k = n / p - 1;
        put += (k * (k + 1) / 2) * p + (n - (k + 1) * p + 1) * (k + 1);
    }
    return put;
}
int solve_query(int n, int b){
    int mic = 1, ans = LONG_LONG_MAX, copie = b;
    for (auto it:pr){
        if (it * it > b)
            break;
        int cnt = 0;
        while (copie % it == 0){
            copie /= it;
            cnt++;
        }
        if (cnt)
            ans = min(ans, countt(n, it) / cnt);
    }
    if (copie > 1)
        ans = min(ans, countt(n, copie));
    return ans;
}
signed main(){
    int n, b;
    sieve();
    while(fin >> n >> b)
         fout << solve_query(n, b) << "\n";
    return 0;
}