高速な素数生成アルゴリズム

Question

CodeIQの、素数の度数分布表を作る問題を解いています。
もちろん答えを教えてもらったり、掲載することはルール違反なので、直接的なことを聞くつもりはないんですが、

エラトステネスの篩を使って、10000以下の素数を求めるとなると、それだけで数秒はかかってしまいます。
VirtualBoxで実行したからとは言っても、遅すぎてCodeIQではタイムアウトになってしまいます。

エラトステネスの篩は知っていたので使ってみたのですが、これ以外で素数生成のよく使われるアルゴリズムはありますでしょうか？

そもそも速度がほしいプログラムをRubyで実装したのが間違いなんでしょうか？

def generate_prime_numbers(n)
	numbers = (2..n).to_a
	limit = Math.sqrt(n)
	prime_numbers = []
	
	while numbers[0] < limit
		prime_numbers << numbers.shift
		
		numbers.each do |i|
			numbers.delete(i) if i % prime_numbers.last == 0
		end
	end
	
	prime_numbers.concat(numbers)
	
	prime_numbers
end

Answer 1

エラトステネスの篩よりも速いアルゴリズムはあるかというと、あります。アトキンの篩というアルゴリズムが2003年に発表されました。エラトステネスの篩の計算量はO(n log log n)ですが、アトキンの篩はO(n/log log n)になるそうです。では、アトキンの篩に変えれば速くなるのかというと、そうとも限りません。速度の違いが出るのがnがかない大きくなってからです。nが高々10000ぐらいであれば、アルゴリズムが単純な分、エラトステネスの篩が速くなると思われます。
※ 実際、ネット上に転がっていたアトキンの篩と、私が実装したエラトステネスの篩で10000で比較したところ、わずかにエラトステネスの篩の方が速かったです。

では、何が間違ってそんなに遅いのかを考えなければなりません。注意すべき事は二つです。

1. 各メソッドは計算量が同じではありません。速いメソッドもあれば、遅いメソッドもあります。
2. 全てについて検査を走らせることは無駄な場合が多いです。飛ばし飛ばしで見れないかを考えてください。

まず、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と同じ速度、むしろ越えるぐらいを目指してみましょう。

Answer 2

自分で実装する必要自体、ないかもしれません。

Rubyには標準でprimeライブラリが添付されていますので、これを使えば素数表も一瞬で作れます。

require 'prime'

Prime.each(n).to_a

Comments

[akamakku]

知らないことだらけです。
ありがとうございます。

[maisumakun]

Rubyのインストール先のlib/ruby/（バージョン）/以下にprime.rbという名前でファイルが入っていますので、中身はそれで確認できます（純粋なRubyでした）。

Answer 3

参考情報

• 汎用的でけっこう速い素数無限列挙 http://antimon2.hatenablog.jp/entry/2012/06/18/231118
• 上限を決めずに素数を生成の高速化(Ruby版) http://log.ttsky.net/article/19515687.html