【Ruby】素数判定の全手法5選

Rubyを使った素数判定のコード例のスクリーンショットRuby
この記事は約9分で読めます。

 

【サイト内のコードはご自由に個人利用・商用利用いただけます】

この記事では、プログラムの基礎知識を前提に話を進めています。

説明のためのコードや、サンプルコードもありますので、もちろん初心者でも理解できるように表現してあります。

基本的な知識があればカスタムコードを使って機能追加、目的を達成できるように作ってあります。

※この記事は、一般的にプロフェッショナルの指標とされる『実務経験10,000時間以上』を凌駕する現役のプログラマチームによって監修されています。

サイト内のコードを共有する場合は、参照元として引用して下さいますと幸いです

※Japanシーモアは、常に解説内容のわかりやすさや記事の品質に注力しております。不具合、分かりにくい説明や不適切な表現、動かないコードなど気になることがございましたら、記事の品質向上の為にお問い合わせフォームにてご共有いただけますと幸いです。
(送信された情報は、プライバシーポリシーのもと、厳正に取扱い、処分させていただきます。)

はじめに

Rubyでのプログラミングにおいて、素数判定はよく遭遇する課題の一つです。

素数という特殊な数字を判定する方法はいくつかありますが、それぞれの方法はその状況に応じて最適な解答を導き出します。

この記事を読むことで、「Rubyでの素数判定」について理解が深まり、自身でコードを書く際の参考になるでしょう。

●素数とは

素数は、1とその数自身以外に約数を持たない正の整数です。

つまり、2つの異なる正の約数だけを持つ数のことを指します。

例えば、2, 3, 5, 7, 11, 13 などが素数です。

●Rubyでの素数判定の基本

Rubyで素数を判定する基本的な方法は、ある数Nが素数であるかを確認するには、1より大きくN未満の全ての数でNを割ってみるというものです。

もしNを割り切る数が存在しなければ、その数は素数です。

○素数判定方法1:自作関数を用いる

まずは、自分で素数判定の関数を作ってみましょう。

def prime?(n)
  return false if n < 2
  (2..Math.sqrt(n)).each do |i|
    return false if n % i == 0
  end
  return true
end

puts prime?(7)  # 素数であるため、trueを返します。
puts prime?(6)  # 素数ではないため、falseを返します。

このコードでは、prime?という関数を定義して素数判定を行っています。

この例では、引数nが2未満の場合は素数ではないため、すぐにfalseを返します。

それ以外の場合は、2からnの平方根までの全ての整数でnが割り切れるかを調べます。

もし割り切れる整数があればnは素数ではないため、falseを返します。

全ての整数で割り切れなかった場合、nは素数であるため、trueを返します。

○素数判定方法2:Rubyの組み込み関数を用いる

次に、Rubyの組み込み関数Prime.prime?を使った素数判定方法を見てみましょう。

この関数は引数が素数であるかどうかを判定します。

require 'prime'

puts Prime.prime?(7)  # 素数であるため、trueを返します。
puts Prime.prime?(6)  # 素数ではないため、falseを返します。

このコードでは、Prime.prime?を使って素数判定を行っています。

この例では、76が素数であるかを判定しています。7は素数であるため、trueを返します。

一方、6は素数ではないため、falseを返します。

○素数判定方法3:エラトステネスの篩

エラトステネスの篩は、古代ギリシャの数学者エラトステネスにちなんで名付けられた素数を見つけるための方法です。

この方法では、ある数までのすべての素数を効率よく見つけることができます。

def eratosthenes(n)
  numbers = [0, 0] + (2..n).to_a
  (2..Math.sqrt(n)).each do |i|
    if numbers[i] != 0
      (i**2..n).step(i){|j| numbers[j] = 0}
    end
  end
  numbers.reject{|num| num == 0}
end

puts eratosthenes(30)  # 30以下の素数を返します。

このコードでは、eratosthenesという関数を使ってエラトステネスの篩を実行しています。

この例では、2から引数nまでの数値を配列に格納しています。

次に、2からnの平方根までの数値に対して、それぞれの数値の倍数を配列から除去しています。

最後に、配列から0を除去し、0以外の数値、つまり素数のリストを返します。

○素数判定方法4:6k法

6k法は素数判定の高速化を図るための手法です。

素数は形式6k±1(kは自然数)に表すことができるという性質を利用した方法です。

def prime_6k?(n)
  return n == 2 || n == 3 if n <= 3
  return false if n % 2 == 0 || n % 3 == 0
  i = 5
  while i * i <= n
    return false if n % i == 0 || n % (i + 2) == 0
    i += 6
  end
  true
end

puts prime_6k?(7)  # 素数であるため、trueを返します。
puts prime_6k?(6)  # 素数ではないため、falseを返します。

このコードでは、prime_6k?という関数を使って素数判定を行っています。

この例では、まず引数nが2または3の場合はそれらは素数なので、すぐにtrueを返します。

それ以外の場合は、nが2または3の倍数である場合はすぐにfalseを返します。

その後、inの平方根以下の間、niまたはi+2で割り切れる場合はfalseを返します。

iはループの各ステップで6ずつ増加します。この関数は、nが素数である場合にtrueを返します。

以上のコードを実行すると、”7″は素数なのでtrueを返し、”6″は素数ではないのでfalseを返します。

○素数判定方法5:ミラー-ロビン法

ミラー-ロビン法は、確率的素数判定法の一つで、大きな数値を対象としたときに高速に動作します。

ただし、その結果は確定的ではなく、一定の確率で誤りを含む可能性がある点には注意が必要です。

def miller_rabin(n, k=5)
  return false if n < 2
  return true if n == 2
  return false if n % 2 == 0
  d = n - 1
  d >>= 1 while d % 2 == 0
  k.times do
    a = rand(n-1) + 1
    t = d
    y = ModMath.pow(a, t, n)  # a^t mod n
    while t != n - 1 and y != 1 and y != n - 1
      y = (y * y) % n
      t <<= 1
    end
    return false if y != n - 1 and t % 2 == 0
  end
  true
end

puts miller_rabin(561)  # 素数ではないため、falseを返す可能性が高いです。
puts miller_rabin(563)  # 素数であるため、trueを返す可能性が高いです。

このコードでは、miller_rabinという関数を使ってミラー-ロビンの素数判定法を実行しています。

この例では、まず引数nが2未満の場合や偶数の場合はすぐにfalseを返します。

それ以外の場合は、n-1dとして保持し、dが偶数である限りdを2で割り続けます。次に、k回の試行を行います。

各試行では、1からn-1までのランダムな数aを選び、ad乗したものをnで割った余りyを計算します。

そして、tn-1になるか、yが1またはn-1になるまで、yを二乗し、tを2倍しています。

これが一連の素数判定の過程です。

●注意点と対処法

どの素数判定方法を選択するかは、その利用シーンによります。

例えば、確実性が必要な場合や小さな数値を扱う場合には、エラトステネスの篩や6k法が適しています。

一方、大きな数値を素早く判定したい場合には、ミラー-ロビン法が適していますが、その結果には一定の不確実性が含まれる点に注意が必要です。

それぞれのメリット・デメリットを理解し、適切な方法を選びましょう。

●素数判定の応用例

素数判定は単に数値が素数であるかどうかを知るためだけのものではなく、その背後には多くの重要な応用例が存在します。

ここでは、その一部を紹介します。

最初に、暗号技術の領域での応用です。

例えば、公開鍵暗号の一種であるRSA暗号では、大きな素数のペアが鍵生成の基盤となります。

大きな素数を効率よく生成するためには、素数判定が欠かせません。

次に、数学的な問題解決における応用です。

素数はその性質上、数列や方程式の特性を理解するための手がかりとなることが多いです。

では、素数判定を実際に応用したコードの例を見てみましょう。

ここでは、1から100までの数字の中で素数のみを抽出し、その素数のリストを出力するRubyのコードを表します。

def prime?(n)
  return false if n < 2
  return true if n == 2
  return false if n % 2 == 0
  i = 3
  while i * i <= n
    return false if n % i == 0
    i += 2
  end
  true
end

def primes_to(n)
  primes = []
  for i in 1..n
    primes << i if prime?(i)
  end
  primes
end

p primes_to(100)

このコードでは、まずprime?という関数を使って素数判定を行っています。

次に、primes_to関数を使って1から指定した数値までの範囲の中で素数のみを抽出し、その素数のリストを返しています。

この例では、1から100までの数字の中で素数のみを抽出し、そのリストを出力しています。

実行結果は、1から100までの間の全ての素数のリストとなります。

まとめ

今回は、Rubyを使用して素数を判定する5つの方法を解説しました。

初心者でも理解できるように、各方法のコードとそれぞれの詳細な解説を交えて紹介しました。

私たちが探訪した素数判定の方法は、単純な方法から始めて、より複雑で高速なアルゴリズムに進んでいきました。

それぞれの方法は、特定の状況や要件に最適なものが異なります。

素数判定は、プログラミングだけでなく、暗号技術や数学的問題解決においても重要な役割を果たします。

そしてそれぞれの方法を理解し、適切な状況で使い分けることが、効率的なプログラムを作るためのキーとなります。

最後に紹介した応用例では、素数判定を利用して、1から100までの素数のリストを出力するRubyのコードを示しました。

これは一例であり、あなた自身がこれらの方法を自分のプロジェクトに適用してみてください。

今後もプログラミングに関する知識を深めるために、さまざまなアルゴリズムやプログラミングテクニックを学んでいきましょう。

プログラミングは、常に新しいことを学び、新たな問題解決の方法を探し続ける旅です。

今回の記事が、あなたのRubyでの素数判定の学習に役立つことを願っています。

また、あなたがRubyの力を引き出し、素数判定の技術をさらに活用するためのステップとなることを期待しています。