エラトステネスの篩
(math/prime/eratosthenes.hpp)

• View this file on GitHub
• Last update: 2020-08-24 20:00:55+09:00
• Include: #include "math/prime/eratosthenes.hpp"

概要

$n$以下の素数判定を高速に行う.

計算量

$O(n\log\log{n})$

使用例

• eratosthenes(n) : $n$以下の自然数に対して求める.
  • 返り値の型 : vector<bool>

Verified with

• test/aoj/ALDS1_1_C.eratosthenes.test.cpp

Code

/**
* @brief エラトステネスの篩
* @docs docs/math/prime/eratosthenes.md
*/

vector<bool> eratosthenes(const int n) {
    vector<bool> r(n + 1, true);
    for (int i = 2; i * i <= n; ++i) {
        if (r[i]) {
            for (int j = i * 2; j <= n; j += i) r[j] = false;
        }
    }
    if (r.size() > 2) {
        r[0] = r[1] = false;
    } else if (r.size() > 1) {
        r[0] = false;
    }
    return r;
}

#line 1 "math/prime/eratosthenes.hpp"
/**
* @brief エラトステネスの篩
* @docs docs/math/prime/eratosthenes.md
*/

vector<bool> eratosthenes(const int n) {
    vector<bool> r(n + 1, true);
    for (int i = 2; i * i <= n; ++i) {
        if (r[i]) {
            for (int j = i * 2; j <= n; j += i) r[j] = false;
        }
    }
    if (r.size() > 2) {
        r[0] = r[1] = false;
    } else if (r.size() > 1) {
        r[0] = false;
    }
    return r;
}

Back to top page