#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("zero2.in");
ofstream g ("zero2.out");

const int NMAX = 100000 + 1;

int n, b, nr, b2;
int divizori[NMAX], putere[NMAX];

void descompune() {
    nr = 0;
    int p;
    b2 = b;
    for (int d = 2; d * d <= b; d++) {
        p = 0;
        while (b % d == 0) {
            b /= d; p++;
        }
        if (p != 0) {
            divizori[++nr] = d;
            putere[nr] = p;
        }
    }
    if (b != 1) {
        divizori[++nr] = b;
        putere[nr] = 1;
    }
}


void rezolva() {
    int divizor, aparitii, sol, minim = 0x7fffffff;
    for (int i = 1; i <= nr; i++) {
        sol = 0;
        divizor = divizori[i];
        while (divizor <= n) {
            aparitii = n / divizor;
            sol = sol + (aparitii - 1) * aparitii / 2 * divizor + aparitii * (n - aparitii * divizor + 1);
            divizor *= divizori[i];
        }
        if (sol / putere[i] <= minim) minim = sol / putere[i];
    }
    g << minim << '\n';
}

int main() {
    int t = 10;
    while (t--) {
        f >> n >> b;
        descompune();
        rezolva();
    }
    return 0;
}