高速な素数の判定(Ruby)

素数は約数を 2個(1 とそれ自身)もつ自然数ですね。ですから、自然数 n が素数かどうかを判定するには、n がそれ自身より小さい自然数(1 を除く)で割ることができるかどうかを確かめればよいわけです。このとき、割る数は を超える必要がないことは明らかです(それを超える数 x で n を割るとき、割れても商は x を超えることはありません。つまり、既に調べています)。この考え方をもとに、以下のような素数判定のメソッドを書くことができます。

def prime?(n)
  return false if n < 2
  return true  if n == 2 or n == 3
  return false if (n % 2).zero?
  3.step(Math.sqrt(n).to_i, 2) {|i| return false if (n % i).zero?}
  true
end

高速化の多少の工夫があって、2以外の偶数はあきらかに素数でないので、先に除外し、3以上の奇数で割っています。これを使って 1~100万の自然数に何個の素数があるか調べてみると*1、自分の環境で 3.1秒程度となり、標準添付ライブラリの Prime クラスの Prime.prime? メソッドを使う(7.0秒程度)より、200%以上高速になります(Ruby 2.3.3)。


さらに高速化することも可能です。割る数として、5以上の場合は 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, ... のように、ステップ幅を 2 と 4 の交互に取っていくという方法です。これはかなりかしこいアルゴリズムで、コードはこんな具合になります。

def prime?(n)
  return false if n < 2
  return true  if n == 2 or n == 3
  return false if (n % 2).zero? or (n % 3).zero?
  i, step = 5, 2
  guard = Math.sqrt(n).to_i
  while i <= guard
    return false if (n % i).zero?
    i += step
    step = 6 - step
  end
  true
end

これで先ほどと同じ計算をしてみると、1.8秒程度とさらに 170% ほど高速化します。Ruby の単純なコードとしては、これで充分なのではないでしょうか。


以下の書籍を参考にしました。

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)


*1:コードはこんな具合です。

co = 0
for i in 1..100_0000
co += 1 if prime?(i)
end
puts co

なお、1~100万までの間の素数の個数を調べるためだけなら、じつは「エラトステネスの篩」を使った方が速いです(0.38秒程度)。得られた配列の大きさがその答えになっているので。(エラトステネスの篩は配列をまとめなおすところが無駄なので、さらなる高速化も可能です。)ただし、エラトステネスの篩はメモリを喰いますし、与えられたひとつの数が素数かどうかを判定するには向きません。
比較的省メモリで「エラトステネスの篩」と同じ結果を得るにはこのようなコードで可能ですが、エラトステネスの篩よりもだいぶ遅くなります。