エラトステネスのふるいを実装してみる - 或るプログラマの開発日記

アルゴリズムに関する知識も自分の中にストックしておきたいということで、今回は「エラトステネスのふるい」について調査したものをメモ。

エラトステネスのふるいとは

素数の一覧を簡易的に求める手法です。

エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。
https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

手法としては極めて簡潔で、2以上の整数のリストから先ず2の倍数を削除し、次に3の倍数をリストから削除、次に5の倍数を削除という具合に小さい素数から順にその合成数を削除するというやり方です。

アルゴリズム

或る整数nまでの素数を求める場合

2からnまでの整数を列挙した探索リストを作成する。
配列の先頭の数を素数リストに移動し、その数の倍数を配列から篩い落とす。
上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
探索リストに残った数を素数リストに移動して処理終了。

以上の要領で処理を行います。

実装

Rubyで実装をしてみました。2からMAX_NUMまでの素数リストを作成、出力するプログラムです。

MAX_NUM = 120
array = (2..MAX_NUM).to_a
x = 2
s = Math::sqrt(MAX_NUM)
loop do
  pn = array.find{|num| num >= x }
  array.delete_if{|num| num != pn && num % pn == 0 }
  break if x >= s
  x += 1
end
p array

実行結果

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]

Rubyの標準モジュールPrime

Rubyでは素数を扱うモジュールが標準で用意されています。
(実は、実装した後にこの事実に気づいた。。(￣▽￣;))

class Prime (Ruby 2.4.0)

require "prime"
p Prime.each(120).to_a
#=>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]

なんだか、車輪の再発明みたいになってしまったが、今回仕組みは理解出来たので良しとしておこうか。