素数の一覧を求めるアルゴリズムのメモ

素数の一覧を求めるアルゴリズムの問題を出されて、良い計算量のアルゴリズムがわからなかったときに調べたメモです。

素数の一覧を求めるアルゴリズム

素数の定義

学術的には不正確かもしれないですが、今回はwikipediaで十分なので、こちらで進めます。

1 より大きい自然数で、正の約数が 1 と自分自身のみであるもの

普通の方法

約数が1以外は自身のみなので、自身より小さい素数で割り切れるものが一つも無ければ、自身は素数となります。

def normal(max_number)
  (2..max_number).each_with_object([]) do |i, primes|
    primes << i if primes.detect {|p| i % p == 0 }.blank?
  end
end

この方法では、計算量がO(N²)になるので効率が悪いです。

エラトステネスの篩(ふるい)

というアルゴリズムがあるそうです。

ステップ 1 探索リストに2からxまでの整数を昇順で入れる。

ステップ 2 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。

ステップ 3 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。

ステップ 4 探索リストに残った数を素数リストに移動して処理終了。

エラトステネスの篩 - Wikipedia

例はwikipediaにも詳しく載ってるので割愛します。

アルゴリズムのイメージ

上に示したステップだけだとよくわからなかったので、腹落ちするように流れを分解して解釈しました。

数字のリストから、素数の小さいものから順にその素数の倍数(ex. 3の場合は 9, 12, 15...)を取り除いていけば、リストに残るのは素数のみになる。
- 素数の1以外の倍数は、素数でないので
また除外する際には、自身の2乗以上の倍数のみでよい。
- 自身より小さい値との組み合わせは既に取り除かれているため(ex. 3の場合は 6は2の倍数なので、取り除かれている)
その倍数として取り除いていく素数の必要最小限の値は、リストの最大値の平方根になる。
- 平方根の値より大きい値との倍数は、リストの最大値を超えるため

実装

def eratosthenes(max_number)
  primes = []
  max_sqrt = Math.sqrt(max_number).to_i
  options = (2..max_number).to_a

  prime = 1
  while prime <= max_sqrt
    prime = options.shift
    primes << prime
    multiples = (max_number / prime - (prime - 1) ).times.map {|m| prime * (m + prime) }
    options = options - multiples
  end
  primes + options
end

結果の比較

MAX_NUMBER = 10000

Benchmark.bm 10 do |r|
  r.report 'normal' do
    normal(MAX_NUMBER)
  end
  r.report 'Eratosthenes' do
    eratosthenes(MAX_NUMBER)
  end
end