Ruby エラトステネスのふるいで学ぶArrayの便利メソッド
素数を求めるアルゴリズム
手順
- 探索リストに2からxまでの整数を昇順で入れる
- 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす
- 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う
- 探索リストに残った数を素数リストに移動して処理終了
Wikipediaのふるってるanim gifがかわいい ww
最初の回答
手順をそのまま書いてみた。
STEP2の倍数をふるい落とすところ、ごちゃごちゃしたので関数に切り出している。
削除する数値を一端リストとして作成している deleting_numbers
class Eratos def self.eratos(max) list = (2..max).to_a prime_check_max = Math.sqrt(max) prime_list = [] begin target = list.shift list = sweep(target, list) prime_list << target end while target < prime_check_max list.count > 0 ? prime_list.concat(list) : prime_list end def self.sweep(target, numbers) max = numbers.last / target deleting_numbers = (1..max).map { |n| n * target } numbers.reject { |n| deleting_numbers.include?(n) } end end
なんか無駄にごちゃごちゃしておる・・
Array.select
ブロックが真を返す要素からなる配列を作成。
例:2で割り切れる数のみ抽出
arr = [ 1, 2, 3, 4, 5 ] arr.select { |n| n % 2 == 0 } # => [ 2, 4 ]
Array.reject
selectの逆
ブロックが偽を返す要素からなる配列を作成。
例:2で割り切れない数のみ抽出
arr = [ 1, 2, 3, 4, 5 ] arr.reject { |n| n % 2 == 0 } # => [ 1, 3, 5 ]
Array.delete_if
ブロックの戻り値が真になった要素を削除
元の配列を操作する
arr = [ 1, 2, 3, 4, 5 ] arr.delete_if { |n| n % 2 == 0 } puts arr # => [ 1, 3, 5 ]
select の逆版 reject を発見してなんか嬉しい♪
もっとすっきり
STEP2の倍数をふるい落とすところ、一端削除する数値のリストを生成してるけど、要するに割り切れる場合はふるい落としてよいことに気づく。
def self.eratos(max) list = (2..max).to_a prime_check_max = Math.sqrt(max) prime_list = [] begin target = list.shift prime_list << target list.delete_if { |n| (n % target).zero? } end while target < prime_check_max list.count > 0 ? prime_list.concat(list) : prime_list end
delete_ifで破壊的に配列を操作。
結局 sweep
部分は1行になったので、関数に分割するのやめた。