はじめに
こんにちは！アメリカの大学で語学を学びながら、独学でソフトウェアエンジニアを目指している者です。
本日は「たのしいRuby 第6版」という教材の中で「素数を判定するメソッドを作成せよ」という練習問題に挑戦してみたのですが、Rubyには他にも素数を求める方法があるのか気になり、記事にしてまとめてみました。
素数を求める方法
教材で紹介されていた方法では、素数を判定するメソッドを自分で作ることが求められていましたが、素数を効率よく判定するにはいくつか重要なポイントがあります。
特に次の点を理解すると、素数判定がより効率的に行えるようになります。
- ある自然数$N$が合成数であれば、$N$は$\sqrt{N}$以下の範囲に素因数を少なくとも1つ持つ。
例えば、N = 49の場合、素数かどうかを調べるには7以下の数で割り切れるかを確認すれば十分です（7 x 7 = 49）。
数学が得意な方は知っているかもしれませんが、素数にはこのような特徴があるため、素数を求める方法も工夫できます。
以下に、いくつかの素数判定方法を紹介します
- $\sqrt{N}$の範囲で判定する方法
- Rubyの標準ライブラリ
primeクラスを使用 - 単純な除算チェック法
- エラトステネスの篩（ふるい）法
$\sqrt{N}$の範囲で判定する方法
教材ではこちらの方法が紹介されていました。
指定した数Nが素数かどうかを、2から$\sqrt{N}$までの数で割り切れるかを確認することで判断します。
def prime?(num)
return false if num < 2
2.upto(Integer.sqrt(num)) do |i|
if num % i == 0
return false
end
end
return true
end
puts prime?(7)
この方法のポイントは、平方根以下の範囲だけをチェックするため、計算量を抑えられることです。
ちなみにMathモジュールではなくIntegerクラスメソッドを使用する理由についてはこちらがとても分かりやすいのでご覧ください
Rubyの標準ライブラリprimeクラスを使用
Rubyには、素数を効率よく扱うための Prime クラスが標準で用意されています。
このクラスを利用すると、素数の判定や特定範囲の素数リストの取得が簡単にできます。
手軽で速度も速いため、素数判定にはよく使用されます。
require 'prime'
# 素数判定
puts Prime.prime?(7) # => true
puts Prime.prime?(10) # => false
# 素数のリストを取得
p Prime.each(30).to_a # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Prime クラス内部では、エラトステネスの篩（ふるい）などの効率的な手法が組み込まれているため、範囲指定で素数リストを取得する場合には速度が速くなるようです。
ただし、単一の数の素数判定に関しては、計算のオーバーヘッドがあるため、場合によっては上記の平方根を用いた方法よりも遅くなる可能性があります。
単純な除算チェック法
2からnum - 1までの範囲で、指定した数が割り切れるかを一つずつ確認する方法です。シンプルですが計算量が大きくなるため、大きな数を判定する際には非効率です。
def is_prime?(num)
return false if num < 2
(2...num).each do |i|
return false if num % i == 0
end
true
end
puts is_prime?(7) # => true
puts is_prime?(10) # => false
エラトステネスの篩
エラトステネスの篩自体は理解できたのですが、コードがとても難しかったので、エラトステネスの篩の説明だけこちらに載せておきます
エラトステネスの篩は特定の範囲内のすべての素数を求める時に有効な方法です
- まず2から始め、倍数をすべて削除します。
- 次の未削除の数に移り、再びその倍数を削除していきます。
- この処理を繰り返して、消去されずに残った数が素数となります。
以下のサイトがとてもわかりやすかったので詳細を知りたい方は見てみてください
まとめ
今回は、Rubyで素数を判定する方法について解説しました。以下に各手法の特長をまとめます。
素数判定をする際はPrimeクラスを使っていておけば速さ的にも間違いはないと思います。