説明

素数テーブルを求める。

計算量

  • $O(N \log \log N)$

実装例

  • prime_table($n$):= $n$ 以下の素数テーブルを返す。$i$ 番目の要素が $true$ のとき $i$ が素数であることを表す。
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;
}

検証

AOJ ALDS_1_1_C 素数

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C"

#include "../../template/template.cpp"

#include "../prime-table.cpp"

int main() {
  auto t = prime_table(100000000);
  int N;
  cin >> N;
  int ret = 0;
  while(N--) {
    int x;
    cin >> x;
    ret += t[x];
  }
  cout << ret << endl;
}