#include <iostream>
#include <fstream>
#include <bitset>
#include <cmath>

using namespace std;

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

long long int solve(long long int n, long long int p){
    long long int k, sol = 0;
    for(long long int x = p; x <= n; x *= p){
        k = n / x - 1;
        sol += k * (k + 1) * x / 2 + (k + 1) * (n - (k + 1) * x + 1);
    }
    return sol;
}

int main(){
    int t = 10;
    long long int n, b, ans, k;
    while(t--){
        fin >> n >> b;
        ans = INFINITY;
        for(int i = 2; i * i <= b; i++){
            if(b % i == 0){
                k = 0;
                while(b % i == 0){
                    b /= i;
                    k++;
                }
                ans = min(ans, solve(n, i) / k);
            }
        }
        if(b > 1){
            ans = min(ans, solve(n, b));
        }
        fout << ans << "\n";
    }
    return 0;
}