Src/Number/PrimeFactorize.hpp

View this file on GitHub
Last update: 2024-06-30 19:07:00+09:00
Include: #include "Src/Number/PrimeFactorize.hpp"

Depends on

Verified with

Code

#pragma once

#include "../Template/TypeAlias.hpp"
#include "./PrimeFactor.hpp"

#include <cassert>
#include <type_traits>
#include <utility>
#include <vector>

namespace zawa {

template <class T>
std::vector<PrimeFactor<T>> PrimeFactorize(T x) {
    static_assert(std::is_unsigned_v<T>, "T must be unsigned integer");
    assert(x > T{0});
    std::vector<PrimeFactor<T>> res;
    for (T f{2} ; u64{f} * f <= x ; f++) {
        u32 exp{};
        while (x % f == 0) {
            exp++;
            x /= f;
        }
        if (exp) {
            res.emplace_back(f, exp);
        }
    }
    if (x > T{1}) {
        res.emplace_back(x, u32{1});
    }
    return res;
}

} // namespace zawa

#line 2 "Src/Number/PrimeFactorize.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Number/PrimeFactor.hpp"

#line 4 "Src/Number/PrimeFactor.hpp"

#include <type_traits>

namespace zawa {

template <class T>
class PrimeFactor {
    static_assert(std::is_unsigned_v<T>, "T must be unsigned integer");
private:
    T factor_{};
    u32 exponent_{};

public: 
    PrimeFactor() = default;

    PrimeFactor(T factor, u32 exponent) : factor_{factor}, exponent_{exponent} {}

    inline T factor() const noexcept {
        return factor_;
    }

    inline u32 exponent() const noexcept {
        return exponent_;
    }

    friend bool operator<(const PrimeFactor<T>& lhs, const PrimeFactor<T>& rhs) {
        return lhs.factor() != rhs.factor() ?
            lhs.factor() < rhs.factor() :
            lhs.exponent() < rhs.exponent();
    }

    friend bool operator>(const PrimeFactor<T>& lhs, const PrimeFactor<T>& rhs) {
        return lhs.factor() != rhs.factor() ?
            lhs.factor() > rhs.factor() :
            lhs.exponent() > rhs.exponent();
    }
};

} // namespace zawa
#line 5 "Src/Number/PrimeFactorize.hpp"

#include <cassert>
#line 8 "Src/Number/PrimeFactorize.hpp"
#include <utility>
#include <vector>

namespace zawa {

template <class T>
std::vector<PrimeFactor<T>> PrimeFactorize(T x) {
    static_assert(std::is_unsigned_v<T>, "T must be unsigned integer");
    assert(x > T{0});
    std::vector<PrimeFactor<T>> res;
    for (T f{2} ; u64{f} * f <= x ; f++) {
        u32 exp{};
        while (x % f == 0) {
            exp++;
            x /= f;
        }
        if (exp) {
            res.emplace_back(f, exp);
        }
    }
    if (x > T{1}) {
        res.emplace_back(x, u32{1});
    }
    return res;
}

} // namespace zawa