【学習ログ】【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 > sqrt
でtarget
が10よりも大きくなったら処理を終了
⑦numbers.delete_if { |num| num % target == 0 }
で、残ったnumbers
の数からtarget
(2, 3, 5, 7
)で割り切れる数を削除する。
⑧primes.concat(numbers)
処理でprimes
とnumbers
を結合させる。
本日は以上となります。
最後までお読みくださりありがとうございました。
Follow @punibastet