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

はじめに
●素数とは
●Rubyでの素数判定の基本
●注意点と対処法
●素数判定の応用例
まとめ

はじめに

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?を使って素数判定を行っています。

この例では、7と6が素数であるかを判定しています。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を返します。

その後、iがnの平方根以下の間、nがiまたは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-1をdとして保持し、dが偶数である限りdを2で割り続けます。次に、k回の試行を行います。

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

そして、tがn-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までの間の全ての素数のリストとなります。