This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/number-theory/prime-table.hpp"
エラトステネスの篩により $n$ 以下の全ての値について素数かどうかを判定する.
prime_table(n)
: $n$ 以下の全ての値について素数かどうか判定するための長さ $n + 1$ の配列を返す. $i$ が素数のとき $i$ 番目の要素は true
で, 非素数のとき false
が格納される./**
* @brief Prime Table(素数テーブル)
*
*/
vector<bool> prime_table(int n) {
vector<bool> prime(n + 1, true);
if (n >= 0) prime[0] = false;
if (n >= 1) prime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (!prime[i]) continue;
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
return prime;
}
#line 1 "math/number-theory/prime-table.hpp"
/**
* @brief Prime Table(素数テーブル)
*
*/
vector<bool> prime_table(int n) {
vector<bool> prime(n + 1, true);
if (n >= 0) prime[0] = false;
if (n >= 1) prime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (!prime[i]) continue;
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
return prime;
}