math/prime_factorize_table.hpp

• View this file on GitHub
• Last update: 2025-04-05 12:46:42+09:00
• Include: #include "math/prime_factorize_table.hpp"

Depends on

• math/lpf_table.hpp

Verified with

• verify/unit_test/prime_factorize_table.test.cpp

Code

#ifndef KK2_MATH_PRIME_FACTORIZE_TABLE_HPP
#define KK2_MATH_PRIME_FACTORIZE_TABLE_HPP 1

#include <algorithm>
#include <cassert>
#include <vector>

#include "lpf_table.hpp"

namespace kk2 {

struct FactorizeTable {
  private:
    static inline std::vector<std::vector<std::pair<int, int>>> _factorize{{}};

  public:
    FactorizeTable() = delete;

    static void set_upper(int m) {
        if ((int)_factorize.size() > m) return;
        int start = std::max<int>(2, _factorize.size());

        LPFTable::set_upper(m);

        _factorize.resize(m + 1);
        for (int n = start; n <= m; ++n) {
            int p = LPFTable::lpf(n);
            if (p == n) {
                _factorize[n] = {
                    {p, 1}
                };
            } else if (n / p % p == 0) {
                _factorize[n] = _factorize[n / p];
                _factorize[n][0].second++;
            } else {
                _factorize[n] = _factorize[n / p];
                _factorize[n].insert(_factorize[n].begin(), {p, 1});
            }
        }
    }

    static const std::vector<std::pair<int, int>> &factorize(int n) {
        assert(n > 0);
        if ((int)_factorize.size() <= n) set_upper(n);
        return _factorize[n];
    }

    static std::vector<int> divisors(int n) {
        assert(n > 0);
        if ((int)_factorize.size() <= n) set_upper(n);
        std::vector<int> res = {1};
        for (auto [p, k] : _factorize[n]) {
            int sz = res.size();
            for (int i = 0; i < sz; ++i) {
                int mul = 1;
                for (int j = 0; j < k; ++j) {
                    mul *= p;
                    res.push_back(res[i] * mul);
                }
            }
        }
        std::sort(res.begin(), res.end());
        return res;
    }
};

} // namespace kk2

#endif // KK2_MATH_PRIME_FACTORIZE_TABLE_HPP

#line 1 "math/prime_factorize_table.hpp"



#include <algorithm>
#include <cassert>
#include <vector>

#line 1 "math/lpf_table.hpp"



#line 6 "math/lpf_table.hpp"
#include <numeric>
#line 8 "math/lpf_table.hpp"

namespace kk2 {

struct LPFTable {
  private:
    static inline std::vector<int> _primes{2}, _lpf{};

  public:
    LPFTable() = delete;

    static void set_upper(int m, int reserve_size = 26355867) {
        if ((int)_lpf.size() == 0) _primes.reserve(reserve_size);
        if ((int)_lpf.size() > m) return;
        m = std::max<int>(2 * _lpf.size(), m);
        _lpf.resize(m + 1);
        iota(_lpf.begin(), _lpf.end(), 0);
        for (int i = 2; i <= m; i++) {
            if (_lpf[i] == i and _primes.back() < i) _primes.emplace_back(i);
            for (const long long p : _primes) {
                if (p * i > m) break;
                if (_lpf[i] < p) break;
                _lpf[p * i] = p;
            }
        }
    }

    static const std::vector<int> &primes() { return _primes; }

    template <typename It> struct PrimeIt {
        It bg, ed;

        PrimeIt(It bg_, It ed_) : bg(bg_), ed(ed_) {}

        It begin() const { return bg; }

        It end() const { return ed; }

        int size() const { return ed - bg; }

        int operator[](int i) const { return bg[i]; }

        std::vector<int> to_vec() const { return std::vector<int>(bg, ed); }
    };

    static auto primes(int n) {
        if (n >= (int)_lpf.size()) set_upper(n);
        return PrimeIt(_primes.begin(), std::upper_bound(_primes.begin(), _primes.end(), n));
    }

    static int lpf(int n) {
        assert(n > 1);
        if (n >= (int)_lpf.size()) set_upper(n);
        return _lpf[n];
    }

    static bool isprime(int n) {
        assert(n > 0);
        if (n >= (int)_lpf.size()) set_upper(n);
        return n != 1 and _lpf[n] == n;
    }
};

} // namespace kk2



#line 9 "math/prime_factorize_table.hpp"

namespace kk2 {

struct FactorizeTable {
  private:
    static inline std::vector<std::vector<std::pair<int, int>>> _factorize{{}};

  public:
    FactorizeTable() = delete;

    static void set_upper(int m) {
        if ((int)_factorize.size() > m) return;
        int start = std::max<int>(2, _factorize.size());

        LPFTable::set_upper(m);

        _factorize.resize(m + 1);
        for (int n = start; n <= m; ++n) {
            int p = LPFTable::lpf(n);
            if (p == n) {
                _factorize[n] = {
                    {p, 1}
                };
            } else if (n / p % p == 0) {
                _factorize[n] = _factorize[n / p];
                _factorize[n][0].second++;
            } else {
                _factorize[n] = _factorize[n / p];
                _factorize[n].insert(_factorize[n].begin(), {p, 1});
            }
        }
    }

    static const std::vector<std::pair<int, int>> &factorize(int n) {
        assert(n > 0);
        if ((int)_factorize.size() <= n) set_upper(n);
        return _factorize[n];
    }

    static std::vector<int> divisors(int n) {
        assert(n > 0);
        if ((int)_factorize.size() <= n) set_upper(n);
        std::vector<int> res = {1};
        for (auto [p, k] : _factorize[n]) {
            int sz = res.size();
            for (int i = 0; i < sz; ++i) {
                int mul = 1;
                for (int j = 0; j < k; ++j) {
                    mul *= p;
                    res.push_back(res[i] * mul);
                }
            }
        }
        std::sort(res.begin(), res.end());
        return res;
    }
};

} // namespace kk2

Back to top page