この間の線形エラトステネスが役に立った

AOJの0222

a, a+2, a+6, a+8が素数となる最大の組を探す問題




ついでに線形エラトステネスの説明も試みてみると、

1. 最初のfor文で素数探索用のテーブルリストを作る。
2. 2つ目のfor文でiと既に探索した素数をかけあわせて、その値は素数でないことをマークする。このときそれよりも小さい素数で既に更新している値が現れたらbreak。各数字は必ず最小の素数がj (厳密にはprime[j]), それで割った値がiのときにのみ更新される。
3. limitに対してそれ以下の最大の素数のインデックスをとってきて、そこから小さい方に条件を満たすかどうか探索する。

2については例えば
i= 4だったらi*j=8, 12が更新される。(i=4, prime=[2,3], array=[0,0,2,3,2])
...
i=8のとき 、i*j=16, 24, 40, 56が更新される。(prime=[2,3,5,7], array=[0,0,2,3,2,5,2,7,2])
i=12のときはi*j=24は既にマークされているのでbreakし36, 60, 82は更新されない。
いつ更新されるかというと36はi=18のときにj=2で更新が行われる。

というわけで各数字は一度しか触られないので、線形。

上位の方々は素数べた書きだったので、素数リスト作るところからやるとこれぐらいが限界なんじゃないかと思った。 メモリをフルに使ったらもう少しいけるのかもしれないけど。

AOJはsubmitごとにprivateとpublicを選べたらいいのにな。
汚いコードはあまり公開したくないし（笑）