Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

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

概要

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

使い方

計算量

Required by

Verified with

Code

/**
 * @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;
}
Back to top page