与えられた数が素数か合成数かを判定する最速の方法(Ruby)

素数を求める方法としてはエラトステネスの篩が有名です。非常にシンプルなアルゴリズムなので簡単に実装できます。
しかし、この方法は2から順に素数を求めていくためのものなので、例えば、30131539が素数か合成数かを判定したいと思ったときに必要以上の計算をすることになります。

なので、ある数が素数か合成数を高速に判定する方法を紹介します。

プログラムだけみたいって人はこちら(wikiからのコピペです) 。
ただし、ごくごく僅かな確率で合成数を素数と判定してしまうことに注意。

class Integer
  def prime?
    n = self.abs()
    return true if n == 2
    return false if n == 1 || n & 1 == 0
    d = n-1
    d >>= 1 while d & 1 == 0
    # 4^(-20)の確率で合成数が素数と判定されることに注意
    # 30.times doにすると、4^(-30)の確率になる
    20.times do
      a = rand(n-2) + 1
      t = d
      y = ModMath.pow(a,t,n)
      while t != n-1 && y != 1 && y != n-1
        y = (y * y) % n
        t <<= 1
      end
      return false if y != n-1 && t & 1 == 0
    end
    return true
  end
end

module ModMath
  def ModMath.pow(base, power, mod)
    result = 1
    while power > 0
      result = (result * base) % mod if power & 1 == 1
      base = (base * base) % mod
      power >>= 1;
    end
    result
  end
end

決定的素数判定法と確率的素数判定法

素数を判定する方法には大きく分けて以下の2種類が存在します

1. 決定的素数判定法 (正確だけど計算量が多い)
   AKS素数判定法(wiki)が有名
2. 確率的素数判定法 (たまーに間違うけど、計算量が劇的に少ない)
   ミラー–ラビン素数判定法(wiki)が有名

確率的素数判定法の中でも最速なのが、ミラー–ラビン素数判定法。
さらに、ミラー–ラビン素数判定法が素数を誤判定する確率は任意にコントロール可能なので、実用的にはこれを使えばOKなはず。

ミラー–ラビン素数判定法

特徴

• 最速の素数判定
  計算量は O(k × log3 n)
• 素数判定を間違う確率をコントロールできる
  4^(-k)の確率

プログラムは上記の通りで、詳細はwikiをみてください！

ちなみに30131539は素数です。