Counts trailing zeroes in `n!` represented in `k`-based numeric system

TrailingZerosCounter.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

std::vector<bool> sieve() {
    std::vector<bool> v(5001, true);
    v[0] = v[1] = false;
    for (int p = 2; p < 5001; p++) {
        if (v[p]) {
            for (int j = 2 * p; j < 5001; j += p)
                v[j] = false;
        }
    }
    return v;
}

std::map<int, int> mults(int n) {
    auto primes = sieve();
    std::map<int, int> mult_freqs;
    int idx = 2;
    while (idx < primes.size() && n > 1) {
        if (primes[idx] && n % idx == 0) {
            n /= idx;
            mult_freqs[idx]++;
        } else {
            idx++;
        }
    }
    return mult_freqs;
}

struct Times {
    int v;
    Times(int n): v(n) {}
    int operator()(std::pair<int, int> p) {
        int n = v;
        int count = 0;
        while (n / p.first > 0) {
            n /= p.first;
            count += n;
        }
        return count / p.second;
    }
};

int main() {
    int n, k;
    std::cin >> n >> k;
    auto mm = mults(k);
    std::vector<int> res(mm.size());
    std::transform(mm.begin(), mm.end(), res.begin(), Times(n));
    int min = *std::min_element(res.begin(), res.end());
    std::cout << min << std::endl;
}