【学習ログ】【Ruby】エラトステネスのふるいプログラム
※このページは過去に自分がRubyの勉強をしたときの学習ログです。誰かの参考になれば幸いです。
目次
エラトステネスのふるいプログラムプログラムをRubyで作成してみた
エラトステネスのふるいとは？
素数を効率的に見つけ出す為のアルゴリズムのこと。
エラトステネスのふるいでは、この素数の性質を利用し、
ある数以下の範囲に存在する素数を探したい場合にその数の平方根より小さい素数の倍数を消して行き、残った数を素数とする。
※素数＝1以上の整数で1とその数自身以外で割り切れない数
例えば、100以下の全ての素数を見つけ出したい場合は、100の平方根である、
10以下の素数の倍数を消して行く。
つまり10以下の素数は、2,3,5,7の4つなので、1から100までの数字の中で2,3,4,7の倍数を消していく。
素数ではない数字が徐々にふるい落とされていく様子から、エラトステネスのふるい と呼ばれている。
平方根とは？
（本当に数学苦手なので、意味わかんないっす・・）
検索してみると、ａ ＝ ｂ ２（自乗）の時、 ａ に対する ｂ のこと。だそう。
※冗談抜きで、この時点で全然飲み込めていない（汗）
その後、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 > sqrt でtargetが10よりも大きくなったら処理を終了
⑦numbers.delete_if { |num| num % target == 0 }で、残ったnumbersの数からtarget（2, 3, 5, 7）で割り切れる数を削除する。
⑧primes.concat(numbers)処理でprimesとnumbersを結合させる。
本日は以上となります。
最後までお読みくださりありがとうございました。
Follow @punibastet
