src/Math/Eratosthenes.hpp

View this file on GitHub
Last update: 2020-04-05 19:54:10+09:00
Include: #include "src/Math/Eratosthenes.hpp"

概要

エラトステネスの篩による素数列挙。計算量は、n以下の素数の逆数和がO(loglog n)であることから、O(n loglog n)である(参考: https://mathtrain.jp/eratosthenes)。

定数倍高速化を頑張るともっとかなり早くなる(参考: https://qiita.com/peria/items/a4ff4ddb3336f7b81d50)

Verified with

test/yosupo/enumerate_primes.test.cpp

Code

/// @docs src/Math/Eratosthenes.md
struct Eratosthenes {
    std::vector<bool> is_prime;
    std::vector<int> primes;
    Eratosthenes(int n) {
        is_prime.assign(n, true);
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i < n; i++) {
            if (!is_prime[i]) continue;
            for (int j = i * 2; j < n; j += i) {
                is_prime[j] = false;
            }
        }
        for (int i = 2; i < n; i++) {
            if (is_prime[i]) primes.push_back(i);
        }
    }
};

#line 1 "src/Math/Eratosthenes.hpp"
/// @docs src/Math/Eratosthenes.md
struct Eratosthenes {
    std::vector<bool> is_prime;
    std::vector<int> primes;
    Eratosthenes(int n) {
        is_prime.assign(n, true);
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i < n; i++) {
            if (!is_prime[i]) continue;
            for (int j = i * 2; j < n; j += i) {
                is_prime[j] = false;
            }
        }
        for (int i = 2; i < n; i++) {
            if (is_prime[i]) primes.push_back(i);
        }
    }
};