素数テーブルをO(n)で構築する
からまでの数が素数であるかどうかの配列(素数テーブル)をで構築する。
はじめに
まず、このような素数テーブルの構築といえばいわゆるエラトステネスのふるいが有名です。小さい方から、その倍数にバツマークを付けていくと、で構築できます。実装も素直で簡単です:
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; } }
実装
次にの実装を見てみます。
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]; } } }
説明
まず、は素数を小さい順に持っています。
そして、という配列が何を情報として持っているのか見ると、mind[x]は「を割り切る1より大きい最小の数」を持っています(0,1は例外)。
ループ内の処理を見ていくと、if文の中はが素数であることが確定しています。すでにまでの処理が終わっていて、この時点でmindの更新が入っていないということはmind[i] = i
であることが確定するということです。
つぎにその下ののループに注目します。これはが素数であるか否かに関係なく回っています。mind[i]を超えない範囲の素数を小さい順に見て行きます。
2つの数の積なので、i*pr[j]
は合成数です。ここで、を割り切る1より大きい最小の数はmind[i]
なので、mind[i*pr[j]] = pr[j]
は正しいです(pr[j] <= mind[i]
なので)。
これがなぜうまくいっているのかについて考えると、合成数は (は素数)の形で表せます。更に、このが選べるものの中で最小であると仮定すると、mind[n] = p
になります。そして、この更新のタイミングは必ずの時にのみ来るということです。なので、mind配列の各indexへのアクセスはちょうど1回なので、この実装がであると分かります。
さいごに
おおよその問題はで十分だと思います。むしろこれが必要になるほどTime Limitがキツい問題はちょっと...
参考
https://codeforces.com/blog/entry/66586 ← ここに実装が書いてあります