素数を爆速で探すアルゴリズム[競プロ]

コード

エラトステネスの篩 ~ Sieve of Eratosthenes

const int N = 1e6;
vector<bool> isPrime(N+1, true);
isPrime[0] = isPrime[1] = false;
for(int i=2; i<N; ++i) {
    if (isPrime[i]) for (int j = i*i; j <= N; j+=i) isPrime[j] = false;
}

素数篩の解説

「そすうふるい」と読むそうです。
これは素数の原則に基づくものです。
はじめに例外処理をしています。0はdummyで、1は定義上素数ではないので。
そして、その他全ての数が素数だと見做して始まります。

1. 数字を倍率に含むものはアウト
2. 重複参照を防ぐ

その意図が込められたforループです。

まとめ

こちらのコードはchatgpt先生に出力してもらいました。
AIでの学習って効率よくて知識欲求が満たされて最高ですよね？
それでは！