This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/number/sieve_of_eratosthenes.hpp"
#ifndef SUISEN_SIEVE_OF_ERATOSTHENES #define SUISEN_SIEVE_OF_ERATOSTHENES #include <cassert> #include <cmath> #include <vector> #include "library/number/internal_eratosthenes.hpp" namespace suisen { template <unsigned int N> class SimpleSieve { private: static constexpr unsigned int siz = N / internal::sieve::PROD + 1; static std::uint8_t flag[siz]; public: SimpleSieve() { using namespace internal::sieve; flag[0] |= 1; unsigned int k_max = (unsigned int) std::sqrt(N + 2) / PROD; for (unsigned int kp = 0; kp <= k_max; ++kp) { for (std::uint8_t bits = ~flag[kp]; bits; bits &= bits - 1) { const std::uint8_t mp = mask_to_index(bits & -bits), m = RM[mp]; unsigned int kr = kp * (PROD * kp + 2 * m) + m * m / PROD; for (std::uint8_t mq = mp; kr < siz; kr += kp * DR[mq] + DF[mp][mq], ++mq &= 7) { flag[kr] |= MASK[mp][mq]; } } } } std::vector<int> prime_list(unsigned int max_val = N) const { using namespace internal::sieve; std::vector<int> res { 2, 3, 5 }; res.reserve(max_val / 25); for (unsigned int i = 0, offset = 0; i < siz and offset < max_val; ++i, offset += PROD) { for (uint8_t f = ~flag[i]; f;) { uint8_t g = f & -f; res.push_back(offset + RM[mask_to_index(g)]); f ^= g; } } while (res.size() and (unsigned int) res.back() > max_val) res.pop_back(); return res; } bool is_prime(const unsigned int p) const { using namespace internal::sieve; switch (p) { case 2: case 3: case 5: return true; default: switch (p % PROD) { case RM[0]: return ((flag[p / PROD] >> 0) & 1) == 0; case RM[1]: return ((flag[p / PROD] >> 1) & 1) == 0; case RM[2]: return ((flag[p / PROD] >> 2) & 1) == 0; case RM[3]: return ((flag[p / PROD] >> 3) & 1) == 0; case RM[4]: return ((flag[p / PROD] >> 4) & 1) == 0; case RM[5]: return ((flag[p / PROD] >> 5) & 1) == 0; case RM[6]: return ((flag[p / PROD] >> 6) & 1) == 0; case RM[7]: return ((flag[p / PROD] >> 7) & 1) == 0; default: return false; } } } }; template <unsigned int N> std::uint8_t SimpleSieve<N>::flag[SimpleSieve<N>::siz]; template <unsigned int N> class Sieve { private: static constexpr unsigned int base_max = (N + 1) * internal::sieve::K / internal::sieve::PROD; static unsigned int pf[base_max + internal::sieve::K]; public: Sieve() { using namespace internal::sieve; pf[0] = 1; unsigned int k_max = ((unsigned int) std::sqrt(N + 1) - 1) / PROD; for (unsigned int kp = 0; kp <= k_max; ++kp) { const int base_i = kp * K, base_act_i = kp * PROD; for (int mp = 0; mp < K; ++mp) { const int m = RM[mp], i = base_i + mp; if (pf[i] == 0) { unsigned int act_i = base_act_i + m; unsigned int base_k = (kp * (PROD * kp + 2 * m) + m * m / PROD) * K; for (std::uint8_t mq = mp; base_k <= base_max; base_k += kp * DRP[mq] + DFP[mp][mq], ++mq &= 7) { pf[base_k + OFFSET[mp][mq]] = act_i; } } } } } bool is_prime(const unsigned int p) const { using namespace internal::sieve; switch (p) { case 2: case 3: case 5: return true; default: switch (p % PROD) { case RM[0]: return pf[p / PROD * K + 0] == 0; case RM[1]: return pf[p / PROD * K + 1] == 0; case RM[2]: return pf[p / PROD * K + 2] == 0; case RM[3]: return pf[p / PROD * K + 3] == 0; case RM[4]: return pf[p / PROD * K + 4] == 0; case RM[5]: return pf[p / PROD * K + 5] == 0; case RM[6]: return pf[p / PROD * K + 6] == 0; case RM[7]: return pf[p / PROD * K + 7] == 0; default: return false; } } } int prime_factor(const unsigned int p) const { using namespace internal::sieve; switch (p % PROD) { case 0: case 2: case 4: case 6: case 8: case 10: case 12: case 14: case 16: case 18: case 20: case 22: case 24: case 26: case 28: return 2; case 3: case 9: case 15: case 21: case 27: return 3; case 5: case 25: return 5; case RM[0]: return pf[p / PROD * K + 0] ? pf[p / PROD * K + 0] : p; case RM[1]: return pf[p / PROD * K + 1] ? pf[p / PROD * K + 1] : p; case RM[2]: return pf[p / PROD * K + 2] ? pf[p / PROD * K + 2] : p; case RM[3]: return pf[p / PROD * K + 3] ? pf[p / PROD * K + 3] : p; case RM[4]: return pf[p / PROD * K + 4] ? pf[p / PROD * K + 4] : p; case RM[5]: return pf[p / PROD * K + 5] ? pf[p / PROD * K + 5] : p; case RM[6]: return pf[p / PROD * K + 6] ? pf[p / PROD * K + 6] : p; case RM[7]: return pf[p / PROD * K + 7] ? pf[p / PROD * K + 7] : p; default: assert(false); } } /** * Returns a vector of `{ prime, index }`. */ std::vector<std::pair<int, int>> factorize(unsigned int n) const { assert(0 < n and n <= N); std::vector<std::pair<int, int>> prime_powers; while (n > 1) { int p = prime_factor(n), c = 0; do { n /= p, ++c; } while (n % p == 0); prime_powers.emplace_back(p, c); } return prime_powers; } /** * Returns the divisors of `n`. * It is NOT guaranteed that the returned vector is sorted. */ std::vector<int> divisors(unsigned int n) const { assert(0 < n and n <= N); std::vector<int> divs { 1 }; for (auto [prime, index] : factorize(n)) { int sz = divs.size(); for (int i = 0; i < sz; ++i) { int d = divs[i]; for (int j = 0; j < index; ++j) { divs.push_back(d *= prime); } } } return divs; } }; template <unsigned int N> unsigned int Sieve<N>::pf[Sieve<N>::base_max + internal::sieve::K]; } // namespace suisen #endif // SUISEN_SIEVE_OF_ERATOSTHENES
#line 1 "library/number/sieve_of_eratosthenes.hpp" #include <cassert> #include <cmath> #include <vector> #line 1 "library/number/internal_eratosthenes.hpp" #include <cstdint> #line 6 "library/number/internal_eratosthenes.hpp" namespace suisen::internal::sieve { constexpr std::uint8_t K = 8; constexpr std::uint8_t PROD = 2 * 3 * 5; constexpr std::uint8_t RM[K] = { 1, 7, 11, 13, 17, 19, 23, 29 }; constexpr std::uint8_t DR[K] = { 6, 4, 2, 4, 2, 4, 6, 2 }; constexpr std::uint8_t DF[K][K] = { { 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 0, 1, 1, 1, 1 }, { 2, 2, 0, 2, 0, 2, 2, 1 }, { 3, 1, 1, 2, 1, 1, 3, 1 }, { 3, 3, 1, 2, 1, 3, 3, 1 }, { 4, 2, 2, 2, 2, 2, 4, 1 }, { 5, 3, 1, 4, 1, 3, 5, 1 }, { 6, 4, 2, 4, 2, 4, 6, 1 }, }; constexpr std::uint8_t DRP[K] = { 48, 32, 16, 32, 16, 32, 48, 16 }; constexpr std::uint8_t DFP[K][K] = { { 0, 0, 0, 0, 0, 0, 0, 8 }, { 8, 8, 8, 0, 8, 8, 8, 8 }, { 16, 16, 0, 16, 0, 16, 16, 8 }, { 24, 8, 8, 16, 8, 8, 24, 8 }, { 24, 24, 8, 16, 8, 24, 24, 8 }, { 32, 16, 16, 16, 16, 16, 32, 8 }, { 40, 24, 8, 32, 8, 24, 40, 8 }, { 48, 32, 16, 32, 16, 32, 48, 8 }, }; constexpr std::uint8_t MASK[K][K] = { { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 }, { 0x02, 0x20, 0x10, 0x01, 0x80, 0x08, 0x04, 0x40 }, { 0x04, 0x10, 0x01, 0x40, 0x02, 0x80, 0x08, 0x20 }, { 0x08, 0x01, 0x40, 0x20, 0x04, 0x02, 0x80, 0x10 }, { 0x10, 0x80, 0x02, 0x04, 0x20, 0x40, 0x01, 0x08 }, { 0x20, 0x08, 0x80, 0x02, 0x40, 0x01, 0x10, 0x04 }, { 0x40, 0x04, 0x08, 0x80, 0x01, 0x10, 0x20, 0x02 }, { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }, }; constexpr std::uint8_t OFFSET[K][K] = { { 0, 1, 2, 3, 4, 5, 6, 7, }, { 1, 5, 4, 0, 7, 3, 2, 6, }, { 2, 4, 0, 6, 1, 7, 3, 5, }, { 3, 0, 6, 5, 2, 1, 7, 4, }, { 4, 7, 1, 2, 5, 6, 0, 3, }, { 5, 3, 7, 1, 6, 0, 4, 2, }, { 6, 2, 3, 7, 0, 4, 5, 1, }, { 7, 6, 5, 4, 3, 2, 1, 0, }, }; constexpr std::uint8_t mask_to_index(const std::uint8_t bits) { switch (bits) { case 1 << 0: return 0; case 1 << 1: return 1; case 1 << 2: return 2; case 1 << 3: return 3; case 1 << 4: return 4; case 1 << 5: return 5; case 1 << 6: return 6; case 1 << 7: return 7; default: assert(false); } } } // namespace suisen::internal::sieve #line 9 "library/number/sieve_of_eratosthenes.hpp" namespace suisen { template <unsigned int N> class SimpleSieve { private: static constexpr unsigned int siz = N / internal::sieve::PROD + 1; static std::uint8_t flag[siz]; public: SimpleSieve() { using namespace internal::sieve; flag[0] |= 1; unsigned int k_max = (unsigned int) std::sqrt(N + 2) / PROD; for (unsigned int kp = 0; kp <= k_max; ++kp) { for (std::uint8_t bits = ~flag[kp]; bits; bits &= bits - 1) { const std::uint8_t mp = mask_to_index(bits & -bits), m = RM[mp]; unsigned int kr = kp * (PROD * kp + 2 * m) + m * m / PROD; for (std::uint8_t mq = mp; kr < siz; kr += kp * DR[mq] + DF[mp][mq], ++mq &= 7) { flag[kr] |= MASK[mp][mq]; } } } } std::vector<int> prime_list(unsigned int max_val = N) const { using namespace internal::sieve; std::vector<int> res { 2, 3, 5 }; res.reserve(max_val / 25); for (unsigned int i = 0, offset = 0; i < siz and offset < max_val; ++i, offset += PROD) { for (uint8_t f = ~flag[i]; f;) { uint8_t g = f & -f; res.push_back(offset + RM[mask_to_index(g)]); f ^= g; } } while (res.size() and (unsigned int) res.back() > max_val) res.pop_back(); return res; } bool is_prime(const unsigned int p) const { using namespace internal::sieve; switch (p) { case 2: case 3: case 5: return true; default: switch (p % PROD) { case RM[0]: return ((flag[p / PROD] >> 0) & 1) == 0; case RM[1]: return ((flag[p / PROD] >> 1) & 1) == 0; case RM[2]: return ((flag[p / PROD] >> 2) & 1) == 0; case RM[3]: return ((flag[p / PROD] >> 3) & 1) == 0; case RM[4]: return ((flag[p / PROD] >> 4) & 1) == 0; case RM[5]: return ((flag[p / PROD] >> 5) & 1) == 0; case RM[6]: return ((flag[p / PROD] >> 6) & 1) == 0; case RM[7]: return ((flag[p / PROD] >> 7) & 1) == 0; default: return false; } } } }; template <unsigned int N> std::uint8_t SimpleSieve<N>::flag[SimpleSieve<N>::siz]; template <unsigned int N> class Sieve { private: static constexpr unsigned int base_max = (N + 1) * internal::sieve::K / internal::sieve::PROD; static unsigned int pf[base_max + internal::sieve::K]; public: Sieve() { using namespace internal::sieve; pf[0] = 1; unsigned int k_max = ((unsigned int) std::sqrt(N + 1) - 1) / PROD; for (unsigned int kp = 0; kp <= k_max; ++kp) { const int base_i = kp * K, base_act_i = kp * PROD; for (int mp = 0; mp < K; ++mp) { const int m = RM[mp], i = base_i + mp; if (pf[i] == 0) { unsigned int act_i = base_act_i + m; unsigned int base_k = (kp * (PROD * kp + 2 * m) + m * m / PROD) * K; for (std::uint8_t mq = mp; base_k <= base_max; base_k += kp * DRP[mq] + DFP[mp][mq], ++mq &= 7) { pf[base_k + OFFSET[mp][mq]] = act_i; } } } } } bool is_prime(const unsigned int p) const { using namespace internal::sieve; switch (p) { case 2: case 3: case 5: return true; default: switch (p % PROD) { case RM[0]: return pf[p / PROD * K + 0] == 0; case RM[1]: return pf[p / PROD * K + 1] == 0; case RM[2]: return pf[p / PROD * K + 2] == 0; case RM[3]: return pf[p / PROD * K + 3] == 0; case RM[4]: return pf[p / PROD * K + 4] == 0; case RM[5]: return pf[p / PROD * K + 5] == 0; case RM[6]: return pf[p / PROD * K + 6] == 0; case RM[7]: return pf[p / PROD * K + 7] == 0; default: return false; } } } int prime_factor(const unsigned int p) const { using namespace internal::sieve; switch (p % PROD) { case 0: case 2: case 4: case 6: case 8: case 10: case 12: case 14: case 16: case 18: case 20: case 22: case 24: case 26: case 28: return 2; case 3: case 9: case 15: case 21: case 27: return 3; case 5: case 25: return 5; case RM[0]: return pf[p / PROD * K + 0] ? pf[p / PROD * K + 0] : p; case RM[1]: return pf[p / PROD * K + 1] ? pf[p / PROD * K + 1] : p; case RM[2]: return pf[p / PROD * K + 2] ? pf[p / PROD * K + 2] : p; case RM[3]: return pf[p / PROD * K + 3] ? pf[p / PROD * K + 3] : p; case RM[4]: return pf[p / PROD * K + 4] ? pf[p / PROD * K + 4] : p; case RM[5]: return pf[p / PROD * K + 5] ? pf[p / PROD * K + 5] : p; case RM[6]: return pf[p / PROD * K + 6] ? pf[p / PROD * K + 6] : p; case RM[7]: return pf[p / PROD * K + 7] ? pf[p / PROD * K + 7] : p; default: assert(false); } } /** * Returns a vector of `{ prime, index }`. */ std::vector<std::pair<int, int>> factorize(unsigned int n) const { assert(0 < n and n <= N); std::vector<std::pair<int, int>> prime_powers; while (n > 1) { int p = prime_factor(n), c = 0; do { n /= p, ++c; } while (n % p == 0); prime_powers.emplace_back(p, c); } return prime_powers; } /** * Returns the divisors of `n`. * It is NOT guaranteed that the returned vector is sorted. */ std::vector<int> divisors(unsigned int n) const { assert(0 < n and n <= N); std::vector<int> divs { 1 }; for (auto [prime, index] : factorize(n)) { int sz = divs.size(); for (int i = 0; i < sz; ++i) { int d = divs[i]; for (int j = 0; j < index; ++j) { divs.push_back(d *= prime); } } } return divs; } }; template <unsigned int N> unsigned int Sieve<N>::pf[Sieve<N>::base_max + internal::sieve::K]; } // namespace suisen