Spaghetti Source - アトキンのふるい

ソースコード void sieve_of_atkin() { int n; for (int z = 1; z <= 5; z += 4) { for (int y = z; y <= sqrtN; y += 6) { for (int x = 1; x <= sqrtN && (n = 4*x*x+y*y) <= N; ++x) isprime[n] = !isprime[n]; for (int x = y+1; x <= sqrtN && (n = 3*x*x-y*y) <= N; x += 2) isprime[n] = !isprime[n]; } } for (int z = 2; z <= 4; z += 2) { for (int y = z; y <= sqrtN; y += 6) { for (int x = 1; x <= sqrtN && (n = 3*x*x+y*

[DummyWitty]

ソースコードがやばいｗ

[gologo13]

エラトステネスのふるいよりも計算量の意味でも実用的な意味でも高速に動作する．

[dominion525]

＞エラトステネスのふるいよりも計算量の意味でも実用的な意味でも高速に動作する．

[pneumaster]

エラトステネスのふるいより高速な素数発見のアルゴリズム

[another]

エラトステネスのふるいより速いそうだ。via http://d.hatena.ne.jp/Gemma/20080402。

[gymno]

"エラトステネスのふるいよりも計算量の意味でも実用的な意味でも高速に動作する．"

[oooooooo]

効率の差は N = 2^23 程度の大きな素数表に対しても高々二倍～三倍なので，エラトステネスからこちらに切り替えたからなんとかなるという，ケースは滅多に無いと思われる．