素数は約数を 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言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)
- 作者: 奥村晴彦
- 出版社/メーカー: 技術評論社
- 発売日: 1991/03/01
- メディア: 単行本
- 購入: 20人 クリック: 396回
- この商品を含むブログ (95件) を見る
追記
標準添付ライブラリの '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秒程度）。得られた配列の大きさがその答えになっているので。（エラトステネスの篩は配列をまとめなおすところが無駄なので、さらなる高速化も可能です。）ただし、エラトステネスの篩はメモリを喰いますし、与えられたひとつの数が素数かどうかを判定するには向きません。
比較的省メモリで「エラトステネスの篩」と同じ結果を得るにはこのようなコードで可能ですが、エラトステネスの篩よりもだいぶ遅くなります。
