Prime Table(素数テーブル)
(math/number-theory/prime-table.hpp)

• View this file on GitHub
• Last update: 2022-09-11 00:53:50+09:00
• Include: #include "math/number-theory/prime-table.hpp"

概要

エラトステネスの篩により $n$ 以下の全ての値について素数かどうかを判定する.

使い方

• prime_table(n): $n$ 以下の全ての値について素数かどうか判定するための長さ $n + 1$ の配列を返す. $i$ が素数のとき $i$ 番目の要素は true で, 非素数のとき false が格納される.

計算量

• $O(n \log \log n)$

Required by

• Enumerate Primes(素数列挙) (math/number-theory/enumerate-primes.hpp)
• Prime Count(素数の個数) (math/number-theory/prime-count.hpp)

Verified with

• test/verify/aoj-alds-1-1-c-2.test.cpp
• test/verify/yosupo-counting-primes.test.cpp
• test/verify/yosupo-enumerate-primes.test.cpp

Code

/**
 * @brief Prime Table(素数テーブル)
 * @docs docs/prime-table.md
 */
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(素数テーブル)
 * @docs docs/prime-table.md
 */
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;
}

Back to top page