http://cr.yp.to/papers/primesieves.pdf
を斜め読みしました。ドメインからわかる通り、 djb が共著なんですよね…アトキンさんが考えたふるいを djb が実装した、って感じですかね、たぶん。
N までの素数を高速に求める方法、って言うと誰でも思いつくのはアリストテレスエラトステネスさんのふるいで、誰でも意味がわかるし速いしでいいものなのですが、それより速くしましたよーという。具体的にはアリストテレスエラトステネス O(N log(N) log(log(N))) に対して O(N / log(log(N))) だそうです。
アイデアとしては、奇数を 4N+1 と 12N+7 と 12N+11 に分類して(4N+1 が 12N+1 と 12N+5 をカバーしてることと、 12N+3 と 12N+9 はどうせ 3 の倍数なんで自明に素数じゃないことを考えるとこの3つの分類で十分)、それぞれに関して、
4で割ると1余るpに対して、 4*x^2+y^2=p の解が奇数個あればpは素数 (必要十分)
みたいな特徴を3つ証明してやって、 x と y に関してループぶん回してやる、みたいな。肝心のその3つの定理の証明はよくわかっとりませんが、なんか書いてあるみたいです(あたりまえ)。
まぁコードを見た感じ計算量はいかにも減りそうですが、実際問題として N/log(log(N)) になる理由とかも何か書いてあるのですがよくわかってません。
あと、空間計算量は O(N^(1/2+O(1)) でできると主張してるのですが、区間ふるいみたいなのをやってやるとそうなる、って話っぽいです。
あと
http://www.prefield.com/algorithm/math/sieve_of_atkin.html
にある比較的わかりやすい実装はどうも djb の実装より結構遅いのですが、いまひとつ djb のコードが読めてなくてなんでかなーと。
わからんわからんばかりですが、まぁ一応こういうものがあるのかーという紹介 desita
