最近学校の授業で、エラトステネスの篩について教わりました。
要するに素数判定アルゴリズムなのですが…

それが下のコード。 結果はというと、もちろんなりました。わーい。
しかも処理（繰り返し）回数が10691回から1549回に激減。
絶対こっちの方がいいじゃん。

教科書はなんでこんなプログラムにしてるのだろうか…
やっぱり教科書プログラムの方がわかりやすくて一般的なんですかね？

エラトステネスですよ。

H2SO5さん＞
きゃー　誤字指摘ありがとうございます　恥ずかしー…

アルゴリズム自体が違うから（エラトステネスとしては）教科書の載せたらいかんでしょ

amehiruneさんが改変したコードは"i*nとi*(n+1)の間の数字はiの倍数ではない"ことを利用したアルゴリズムを使ったものやで
教科書のほうはあくまでもクラシックな、エラトステネスの櫛のアルゴリズムになるんや
エラトステネスの櫛というアルゴリズムはwikiにも乗ってるとおりの動作やから、その部分を変えてしまうとまったくの別のアルゴリズムになるんやで

それにエラトステネスの櫛のオーダーは

n-1+n-2+...+1
=n*(n+1) / 2
=O(n^2)

だけど、amehiruneさんの考えたアルゴリズムでは

n/2+n/3+n/4+...n/sqrt(n)
=n*(1/2+1/3+1/4+...+1/sqrt(n))
=n*Σ_{k=2}^{sqrt(n)}{1/k}
<n*(1*n^(1/2))
=O(n^(3/2))

となって計算量自体もちがうから、素数判定としては同じでも、アルゴリズムとしては違うんやろなぁ……

ちなみにamehiruneさんのほうのオーダーは割りとガバガバでn/2+n/3+n/4+...n/sqrt(n)の部分は実際はもっと軽減できるので、上で示したオーダーよりもかなり小さくなるはずやからすまんの
格項xに対してprime(x)=0となる確立が統計としてあるから確立かけたらいいのかもしれないけど、普通に計算方法があるかもしれないのであしからず

chop.chop さんが書きました:それにエラトステネスの櫛のオーダーは

n-1+n-2+...+1
=n*(n+1) / 2
=O(n^2)

だけど、

そんなまさか、そんなに遅いわけがない！もしそんなに遅かったら全然使われないはずだ！
蟻本 (Google ブックスのプレビュー)の112ページには

エラトステネスの篩の計算量は、O(n log log n)程度であることが知られています。

と書いてあるし…

と思ったけど、よく見たら遅いと主張されているのは
エラトステネスの櫛
か…紛らわしいなあ。

>>みけCATさん

今確認したら、"エラトステネスの櫛"などというアルゴリズムは存在しませんでした…申し訳ない
単に二個目のfor分内でj++としているほうを当職が勝手に櫛などと呼んでいたにすぎませぬ

ただ実装方法によってはO(n^2)かかるのでしょう。それを勘違いしていたのがいけなかった

篩の方が公式です。

篩も櫛もパッと見は分かりづらいのに櫛でも通じそうなアルゴリズムを作ってしまったエラトステネスさんサイドに責任があると主張します（震え声）

chopさん＞
なるほど…アルゴリズムとしては全くの別物なんですね…
にしてもまだ短縮できるとは…
やっぱりプログラムは奥が深いですね！

みけCATさん＞
初期値を振る段階ですでにふるい落とし開始ですか！その発想はなかったです！
自分も計算量を計算してみたらn*log(log n)でしたし…　（というかなんでそんな面倒くさい量に…）
って、櫛←これも「ふるい」って読むんですかね？--;

>>amehiruneさん

いえ、すみません
最初に全く別のアルゴリズムと書きましたが、あれは当職の勘違いです
エラトステネスの篩、というアルゴリズムは一つしか無いのですが、当職がナイーブな方の実装
つまり、教科書に載っている方を勝手に櫛と呼んでいたのです

上の方に出てきているコードは全てエラトステネスの篩というアルゴリズムをベースにしたコードです
ただ、効率化していくと、nlog log nまで抑えられるという話ですね
これは素数の逆数和の定理から、その収束速度を用いて導いてるらしいです
当職の不勉強で混乱させて申し訳ないですを