Prime Factorization

Decomposing an integer into its prime components operates with a time complexity of O(√n). The following implementation accepts an integer val and a boolean flag uniqueOnly. If uniqueOnly is true, the result contains distinct primes only; otherwise, all prime factors including duplicates are returned.

std::vector<long long> getPrimeFactors(long long val, bool uniqueOnly) {
    std::vector<long long> components;
    for (long long i = 2; i * i <= val; ++i) {
        while (val % i == 0) {
            components.push_back(i);
            val /= i;
        }
    }
    if (val > 1) {
        components.push_back(val);
    }
    if (uniqueOnly) {
        components.erase(std::unique(components.begin(), components.end()), components.end());
    }
    return components;
}

Retrieving All Divisors

To list all positive divisors of a number efficiently, an O(√n) approach iterates up to the square root. Using a std::set automatically handles the sorting and deduplication of divisors, such as the pair (i, n/i).

std::vector<long long> getAllDivisors(long long val) {
    std::set<long long> divisors;
    for (long long i = 1; i * i <= val; ++i) {
        if (val % i == 0) {
            divisors.insert(i);
            divisors.insert(val / i);
        }
    }
    return std::vector<long long>(divisors.begin(), divisors.end());
}

Prime Factorization with Exponents

This variant returns a vector of pairs, where each pair represents a prime factor and its corresponding exponent in the prime factorization. For example, decomposing 60 yields pairs for 2 squared, 3 to the power of 1, and 5 to the power of 1.

std::vector<std::pair<long long, int>> primeFactorizationWithExponents(long long val) {
    std::vector<std::pair<long long, int>> result;
    for (long long i = 2; i * i <= val; ++i) {
        if (val % i == 0) {
            int count = 0;
            while (val % i == 0) {
                val /= i;
                count++;
            }
            result.emplace_back(i, count);
        }
    }
    if (val > 1) {
        result.emplace_back(val, 1);
    }
    return result;
}

Factorial Prime Decomposition

Decomposing n! (n factorial) involves determining the exponent of each prime less than or equal to n within the factorial. The implementation uses a sieve for initialization (O(n)), followed by a query function that runs in O(log n * log n) by summing the integer divisions of n by increasing powers of the prime.

struct FactorialDecomposer {
    std::vector<int> primesList;

    // Sieve of Eratosthenes to generate primes up to limit
    void initialize(int limit) {
        std::vector<bool> isPrime(limit + 1, true);
        for (int i = 2; i <= limit; ++i) {
            if (isPrime[i]) {
                primesList.push_back(i);
                for (long long j = (long long)i * i; j <= limit; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    // Returns pairs of {prime, exponent} for n!
    std::vector<std::pair<int, int>> decomposeFactorial(int n) {
        std::vector<std::pair<int, int>> result;
        for (int p : primesList) {
            if (p > n) break;
            int power = 0;
            int current = n;
            while (current) {
                current /= p;
                power += current;
            }
            result.emplace_back(p, power);
        }
        return result;
    }
};