まりぴよこのブログ

日々の日記。技術ネタでまとまりきってないものの記録、伝わる文章の書き方を練習とか。

Ruby エラトステネスのふるいで学ぶArrayの便利メソッド

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

エラトステネスの篩 - Wikipedia

手順

  • 探索リストに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行になったので、関数に分割するのやめた。