Discussion on: Daily Challenge #7 - Factorial Decomposition

[dawagnbr]

C++

struct factor {
    long prime;
    long power;
};

auto decompose_factorial(long n) {
    std::vector<factor> result;
    for (long i = 2; i <= n; ++i) {
        auto prime = true;
        for (auto &f : result) {
            for (auto r = i; r % f.prime == 0; r /= f.prime) {
                prime = false;
                ++f.power;
            }
        }
        if (prime) {
            result.push_back({i, 1});
        }
    }
    return result;
}

int main() {
    long n = 25;
    auto decomposition = decompose_factorial(n);
    std::cout << "n = " << n << std::endl;
    std::cout << "decomp(n!) = ";
    for (auto &f : decomposition) {
        std::cout << f.prime;
        if (f.power > 1) {
            std::cout << "^" << f.power;
        }
        std::cout << " ";
    }
    std::cout << std::endl;
    return EXIT_SUCCESS;
}

Output:

n = 25
decomp(n!) = 2^22 3^10 5^6 7^3 11^2 13 17 19 23