エラトステネスの篩よりも速いアルゴリズムはあるかというと、あります。アトキンの篩というアルゴリズムが2003年に発表されました。エラトステネスの篩の計算量はO(n log log n)ですが、アトキンの篩はO(n/log log n)になるそうです。では、アトキンの篩に変えれば速くなるのかというと、そうとも限りません。速度の違いが出るのがnがかない大きくなってからです。nが高々10000ぐらいであれば、アルゴリズムが単純な分、エラトステネスの篩が速くなると思われます。
※ 実際、ネット上に転がっていたアトキンの篩と、私が実装したエラトステネスの篩で10000で比較したところ、わずかにエラトステネスの篩の方が速かったです。
では、何が間違ってそんなに遅いのかを考えなければなりません。注意すべき事は二つです。
- 各メソッドは計算量が同じではありません。速いメソッドもあれば、遅いメソッドもあります。
- 全てについて検査を走らせることは無駄な場合が多いです。飛ばし飛ばしで見れないかを考えてください。
まず、1.についてです。Array#delete
を使っているところがありますが、Array#delete
はとてつもなく遅いです。考えてみてください。まずは、Arrayにあるすべての要素について一致するか確認します。これだけでO(n)の計算量です。そして、一致しているのが見つかると、そのあとの要素をずらしながら元の配列に入れていく処理をします。
参考: https://github.com/ruby/ruby/blob/trunk/array.c#L2959
つまり、Array#delete
が呼び出されれば呼び出されるほど遅くなります。これでは全体が遅くなっても仕方がありません。よって、Array#delete
を使わない方法を考える必要があります。たとえば、数字の配列からいらない物を削除していくのでは無く、この数字は削除されたと印をつけていくという処理です。つまり、numbers[i] = nil
等とすると言うことです。Array#[]=
はArray#delete
よりも遥かに高速ですので、劇的に速度が変わります。
次に、2.です。ある素数pについてその倍数を除外するとき、残っている数字を全て見る必要はあるのでしょうか?実際除外するのはpの倍数だけです。1倍はそのものですので、2p、3p、4p、…とnを越えるまで確認するだけで済むはずです。残っている数の方が少ないのではと思うかも知れませんが、倍数の方がpが大きければ大きいほど確認する数は減っていきます。見に行き方を工夫するだけで、計算量はかなり変わってきます。
色々見ても、何が遅いかなんてわからない…と言う場合はprofileライブラリを使ってみてください。どのメソッドが何回呼ばれてどれだけかかったのかが確認できます。ボトルネックが何かがわかれば、改善策も見えてきます。
ということで、もう一度考えてみてください。primeライブラリを使えばすぐに終わってしまう物ではありますが、primeと同じ速度、むしろ越えるぐらいを目指してみましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。