【学習ログ】【Ruby】エラトステネスのふるいプログラム

※このページは過去に自分がRubyの勉強をしたときの学習ログです。誰かの参考になれば幸いです。

スポンサーリンク

エラトステネスのふるいプログラムプログラムをRubyで作成してみた

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

素数を効率的に見つけ出す為のアルゴリズムのこと。

エラトステネスのふるいでは、この素数の性質を利用し、
ある数以下の範囲に存在する素数を探したい場合にその数の平方根より小さい素数の倍数を消して行き、残った数を素数とする。

※素数=1以上の整数で1とその数自身以外で割り切れない数

例えば、100以下の全ての素数を見つけ出したい場合は、100の平方根である、
10以下の素数の倍数を消して行く。

つまり10以下の素数は、2,3,5,7の4つなので、1から100までの数字の中で2,3,4,7の倍数を消していく。

素数ではない数字が徐々にふるい落とされていく様子から、
エラトステネスのふるい と呼ばれている。

平方根とは?

(本当に数学苦手なので、意味わかんないっす・・)
検索してみると、a = b 2(自乗)の時、 a に対する b のこと。だそう。

※冗談抜きで、この時点で全然飲み込めていない(汗)

その後、YouTubeの動画の解説を視聴したりして、自乗する前の数のことだということはかろうじて理解した。

(例)10の自乗=100

(ようやく)完成コード

#エラトステネスのふるい
def eratosthenes(number)
  numbers = (2..number).to_a
  primes = [] 
  sqrt = Math.sqrt(number).floor

  while target = numbers.shift
    primes << target

    break if target > sqrt

    numbers.delete_if { |num| num % target == 0 } 
  end
  primes.concat(numbers) 
end

p eratosthenes(100)

実行結果 →[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]

覚えたてのメソッドについて

まずは、覚えたてのメソッドから。

メソッド名役割
Math.sqrt数値の平方根を求める
floor小数の切り捨て
delete_if削除する条件に当てはまる配列の中身を削除
concat配列の結合

Math.sqrt について

理解を早めるために単独で使ってみた。

def square_root(number)
  sqrt = Math.sqrt(number).floor
  return sqrt
end
p square_root(100)

実行結果 → 10

delete_if について

numbers.delete_if { |num| num % target == 0 }

とした場合、num % target == 0に当てはまるものを削除する。
・・っていってもよくわかっていなかったので、別の例を調べてみた。

target = ['hoge', 'fuga','funga','gagi'] # 元となるデータ
list = ['hoge', 'fuga'] # 削除対象の文字列のリスト
  target.delete_if { |str| list.include?(str) }
  #listに含まれている要素を削除する

p target

実行結果 → ["funga", "gagi"]

というわけで、最終的な解説

#エラトステネスのふるい
def eratosthenes(number)
  numbers = (2..number).to_a #2〜numberまでの配列を用意
  primes = [] #素数を入れる配列
  sqrt = Math.sqrt(number).floor #平方根を変数に代入

  while target = numbers.shift #配列の先頭要素を取り出してtarget変数に代入
    primes << target #素数の配列に追加

    break if target > sqrt #配列の先頭がnumber平方根より大きくなったら処理を終える

    numbers.delete_if { |num| num % target == 0 } #素数の倍数を削除
  end
  primes.concat(numbers) #残った要素を素数の配列に追加
end

p eratosthenes(100)

非常にややこしいので、具体的な数字で解説した方がイメージしやすいかもしれない。正確ではないかもしれないが、上記のように引数が100の場合の処理の流れが以下。

numbers = (2..number).to_aの段階では変数numbersには2〜100までの数字が代入される。

②4行目のprimes = []は空の配列。

sqrt = Math.sqrt(number).floorでは100の平方根である10が変数sqrtに代入

while target = numbers.shiftの一度目の処理では配列の先頭要素の2が変数targetに代入。

primes << target で配列primesに素数が代入される。

※途中でp primesと入れてみて結果を確認したらループ処理終了の時点で[2, 3, 5, 7]となったため、理由はイマイチわからないがprimesには10以下の素数が格納されるのは間違いない

break if target > sqrttargetが10よりも大きくなったら処理を終了

numbers.delete_if { |num| num % target == 0 }で、残ったnumbersの数からtarget2, 3, 5, 7)で割り切れる数を削除する。

primes.concat(numbers)処理でprimesnumbersを結合させる。

本日は以上となります。

最後までお読みくださりありがとうございました。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

コメントする