高速な素数の判定（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言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

　

追記

標準添付ライブラリの 'prime' を使う場合、Prime.prime?() を使うより何故か Integer#prime? を使った方が 600% 以上高速になります。なので、これを使った方がよいでしょう。（2019/7/2）

Integer#prime? の実装は以下です（Ruby 2.6.0）。めちゃかしこい。

def prime?
  return self >= 2 if self <= 3
  return true if self == 5
  return false unless 30.gcd(self) == 1
  (7..Integer.sqrt(self)).step(30) do |p|
    return false if
      self%(p)    == 0 || self%(p+4)  == 0 || self%(p+6)  == 0 || self%(p+10) == 0 ||
      self%(p+12) == 0 || self%(p+16) == 0 || self%(p+22) == 0 || self%(p+24) == 0
  end
  true
end

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

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

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