裏紙

ほぼ競プロ、たまに日記

素数テーブルをO(n)で構築する

 1から nまでの数が素数であるかどうかの配列(素数テーブル)を O(n)で構築する。

はじめに

まず、このような素数テーブルの構築といえばいわゆるエラトステネスのふるいが有名です。小さい方から、その倍数にバツマークを付けていくと、 O(nloglogn)で構築できます。実装も素直で簡単です:

const int N = 10000001;
bool prime[N];
void build_sieve(){
    fill(prime,prime+N,true);
    prime[0] = prime[1] = false;
    for(int i=2; i<N; ++i)if(prime[i]){
        for(int j=2*i; j<N; j+=i) prime[j] = false;
    }
}

実装

次に O(n)の実装を見てみます。

const int N = 10000001;
int mind[N];
vector<int> pr;

void build_sieve(){
    mind[0] = mind[1] = 1;
    for(int i=2; i<N; ++i){
        if(mind[i] == 0){
            pr.push_back(i);
            mind[i] = i;
        }
        for (int j=0; j<int(pr.size()) && pr[j]<=mind[i] && i*pr[j]<N; ++j){
            mind[i*pr[j]] = pr[j];
        }    
    }
}

説明

まず、 pr素数を小さい順に持っています。

そして、 mindという配列が何を情報として持っているのか見ると、mind[x]は「 xを割り切る1より大きい最小の数」を持っています(0,1は例外)。

ループ内の処理を見ていくと、if文の中は i素数であることが確定しています。すでに i-1までの処理が終わっていて、この時点でmindの更新が入っていないということはmind[i] = iであることが確定するということです。

つぎにその下の jのループに注目します。これはi素数であるか否かに関係なく回っています。mind[i]を超えない範囲の素数を小さい順に見て行きます。

2つの数の積なので、i*pr[j]合成数です。ここで、 iを割り切る1より大きい最小の数はmind[i]なので、mind[i*pr[j]] = pr[j]は正しいです(pr[j] <= mind[i]なので)。

これがなぜうまくいっているのかについて考えると、合成数 n = m \cdot p ( m \ge 2, p素数)の形で表せます。更に、このpが選べるものの中で最小であると仮定すると、mind[n] = pになります。そして、この更新のタイミングは必ず i=mの時にのみ来るということです。なので、mind配列の各indexへのアクセスはちょうど1回なので、この実装が O(n)であると分かります。

さいごに

おおよその問題は O(nloglogn)で十分だと思います。むしろこれが必要になるほどTime Limitがキツい問題はちょっと...

参考

https://codeforces.com/blog/entry/66586 ← ここに実装が書いてあります

https://codeforces.com/contest/1154/problem/G ← 元ネタの問題です