sieve of Eratosthenes (エラトステネスの篩)
(lib/eratosthenes-sieve.hpp)

• View this file on GitHub
• Last update: 2021-10-06 03:41:28+09:00
• Include: #include "lib/eratosthenes-sieve.hpp"

概要

TBD

使い方

TBD

計算量

TBD

Verified with

• test/verify/yosupo-enumerate-primes.test.cpp

Code

/**
 * @brief sieve of Eratosthenes (エラトステネスの篩)
 * @docs docs/eratosthenes-sieve.md
 */
template<typename T>
class EratosthenesSieve {
public:
    T size;
    std::vector<bool> p;
    EratosthenesSieve(T size) : size(size), p(size + 1, true) {
        p[0] = p[1] = false;
        for (T i = 2; i * i <= size; i++) if (p[i])
            for (T j = i * i; j <= size; j += i)
                p[j] = false;
    }
    std::vector<T> get_primes() const {
        std::vector<T> ret;
        for (T i = 0; i <= size; i++)
            if (p[i]) ret.push_back(i);
        return ret;
    }
};

#line 1 "lib/eratosthenes-sieve.hpp"
/**
 * @brief sieve of Eratosthenes (エラトステネスの篩)
 * @docs docs/eratosthenes-sieve.md
 */
template<typename T>
class EratosthenesSieve {
public:
    T size;
    std::vector<bool> p;
    EratosthenesSieve(T size) : size(size), p(size + 1, true) {
        p[0] = p[1] = false;
        for (T i = 2; i * i <= size; i++) if (p[i])
            for (T j = i * i; j <= size; j += i)
                p[j] = false;
    }
    std::vector<T> get_primes() const {
        std::vector<T> ret;
        for (T i = 0; i <= size; i++)
            if (p[i]) ret.push_back(i);
        return ret;
    }
};

Back to top page