素因数分解

unique_factorization.hpp

#include <iostream>
#include <cstdint>
#include <vector>
#include <cmath>
struct unique_factorization_element {
    std::uint32_t prime;
    std::uint8_t pow;
};
std::ostream& operator<< (std::ostream& os, const unique_factorization_element& e)
{
    os << e.prime << '^' << std::uint16_t(e.pow);
    return os;
}
std::vector<unique_factorization_element> unique_factorization(std::uint64_t n)
{
    std::vector<unique_factorization_element> re;
    re.reserve(20);
    const std::uint32_t lim = std::sqrt(n);
    auto calc_pow = [&n](std::uint32_t prime){
        std::uint8_t re = 0;
        while(!(n % prime)){
            n /= prime;
            ++re;
        }
        return re;
    };
    if(const auto pow = calc_pow(2)) re.push_back({std::uint32_t(2), pow});
    for(std::uint32_t i = 3; i < lim; i += 2){
        if(const auto pow = calc_pow(i)) re.push_back({i, pow});
    }
    re.shrink_to_fit();
    return re;
}