Ruby の正規表現で素数かどうかを確認する方法

作成日 2018.09.11
更新日 2018.09.13

Regex
Ruby

Ruby の正規表現を使って, 素数かどうかを確認するメソッドを作ってみました. パフォーマンスは正直全然良くないのですが, 余興の様なものとしては面白いのではないかと思います. 正規表現の説明もします.

正規表現で素数を確認するメソッド

こちらが Ruby の正規表現で素数かどうかを確認するメソッドになります:

def prime?(n)
  !/^(?:a?|(aa+?)\1+)$/.match?('a' * n)
end

シンプルな正規表現ですが, 本当に素数かどうかを確認することができるのでしょうか.

試しにいくつかの数をそのメソッドを使って確認してみました:

prime?  0  # => false
prime?  1  # => false
prime?  2  # => true
prime?  3  # => true
prime?  4  # => false
prime?  5  # => true
prime?  6  # => false
prime?  7  # => true
prime?  8  # => false
prime?  9  # => false
prime? 10  # => false
prime? 11  # => true
prime? 12  # => false
prime? 13  # => true

見事に 0 から 13 までの数で素数かどうかを確認できています.

ではさらに大きな数でも本当に素数かどうかを確認することができるのでしょうか?

それを確かめるべく, Ruby の標準ライブラリ prime の Prime::prime? クラスメソッドを使って, より大きな数でも本当に素数である場合とそうでない場合とに区別することができるのか確かめてみたいと思います.

早速 0 から 1000 までの数で, prime? が返す真偽値と Prime::prime? が返す真偽値が完全に一致するか次のコードで確認してみました:

(0..1000).all? { |n| prime?(n) == Prime.prime?(n) }  # => true

このように true となり, 0 から 1000 までの数で prime? が返す真偽値と Prime::prime? が返す真偽値は完全に一致しました.

どうやら prime? メソッドは本当に素数かどうかを確認することができるようです.

正規表現の説明

正規表現で素数かどうかを確認する prime? メソッドが, 本当に素数かどうかを確認することができるということを確認できたところで, ではどうしてそのようなことができるのかということを説明させていただきます.

まず先ほどのメソッドですが:

def prime?(n)
  !/^(?:a?|(aa+?)\1+)$/.match?('a' * n)
end

内容は正規表現 /.../ に 'a' * n がマッチしなければ true となり, 素数と確認できるというものです.

逆にマッチする場合, false となり素数ではないとなります.

ではどうして素数のみマッチしないような正規表現パターンになるのでしょうか.

また素数以外の数のみマッチするような正規表現パターンになるのでしょうか.

一つずつ見ていきたいと思います.

まず引数 n の値に応じて match? メソッドに渡される文字列が変化します.

n が 0 の場合は "" となり, n が 1 の場合, "a", 2 の場合, "aa", 3 の場合, "aaa" となっていきます.

正規表現パターン /^(?:a?|(aa+?)\1+)$/ の ^ は文字列の先頭にマッチし, $ は文字列の末尾にマッチします.

(?:...) は本来キャプチャされるグループをキャプチャしないようにして, 少しだけパフォーマンスを良くし, \n による後方参照をしやすくしています.

... の最初の a? は "" か "a" にマッチするので, この時点で n が 0 か 1 の場合, そのパターンにマッチし, false となります.

0 と 1 は素数ではないとして false を返すことができます.

もし n が 0 や 1 でなく, 2, 3, 4, 5 などとなると, a? にはマッチしないので, | で区切られたもう一つのパターン (aa+?)\1+ にマッチするかどうか試みられます.

この正規表現パターンが, n が素数かどうかを確認するための一番重要な部分となります.

例えば n が 2 の場合, (aa+?) の部分が "aa" とマッチしますが, その次の後方参照 \1+ でマッチが失敗します.

\1* ではなく \1+ なので, 与えられる文字列が少なくとも "aaaa" でなくてはならないからです.

なので 2 は true となり, 確かに素数であると処理することができます.

今度は n が 3 の場合, (aa+?) の部分でまず "aa" がマッチしますが, 同じくその次の \1+ でマッチが失敗するので, true となります.

n が 4 の場合, (aa+?) で "aa" がマッチし, 次の \1+ で残りの "aa" がマッチするので, 全体のマッチが成功し false となります.

このように n が 4 以上で偶数の場合, (aa+?) の部分でまず "aa" とマッチし, \1+ の部分で全体のマッチが "aaaa" (4), "aaaaaa" (6), "aaaaaaaa" (8) と "aa" (2) を除く偶数分の "a" にマッチしていくので, 必ず false となります.

いわば, 2 * 2, 2 * 3, 2 * 4 と与えられた文字列の数を因数分解しているようなもので, その因数分解が成功したら false としているようなものです.

今度は n が 5 の場合, (aa+?) で "aa" がマッチし, 次の \1+ でマッチが失敗するのでバックトラックして, (aa+?) のマッチが "aa" から "aaa" となり, 次の \1+ でまたマッチが失敗し, 全体のマッチが失敗し, true となります.

2 * 2, 2 * 3 で因数分解を試みたけれども, 駄目だったので, バックトラックして 3 * 2 で試みたけれども駄目だった, という感じになります.

このように \1+ の部分のマッチが失敗して (aa+?) の部分にバックトラックする度, (aa+?) のマッチが +? による最小量指定子のおかげで "aa" から "aaa", "aaaa", "aaaaa" と一つずつ "a" が増えていくところがポイントです.

なぜなら続く \1+ の部分により, (aa+?) のマッチしている文字列の長さが 2 倍, 3 倍, 4 倍となってマッチが試みられていくからです.

なので (aa+?) と \1+ の組み合わせにより, 実際, 因数分解の総当たりのようなことをしていることになります.

その因数分解の総当たりで因数分解できたら false となり, 因数分解できなかったら true という感じです.

その因数分解ができるということは, n は素数ではないと判断することができます.

なぜなら, 一つの因数の最小値は (aa+?) の部分で 2 となり, もう一つの因数の最小値も \1+ により 2 となるため, その様な因数分解では, 正の約数が 1 と自分自身のみであるものという素数の条件を満たさないことになるからです.

それゆえに /^(?:a?|(aa+?)\1+)$/ という正規表現パターンで素数かどうかを確認することができるのですね.

凄いですね正規表現.

例外処理

ちなみに, その prime? メソッドですが:

def prime?(n)
  !/^(?:a?|(aa+?)\1+)$/.match?('a' * n)
end

与えられる n の値が 0 より小さい場合, 'a' * n の部分で次の例外が発生します:

prime? -1 rescue $!  # => #<ArgumentError: negative argument>

なので実質的に n が素数かどうかを確認するメソッドとして機能しています.

間違っても true は返りませんので.

もし例外ではなく false を返す場合は次の様にできます:

def prime?(n)
  return false if n < 0
  !/^(?:a?|(aa+?)\1+)$/.match?('a' * n)
end

prime? -1  # => false

n に Integer インスタンスオブジェクト以外のオブジェクトが渡されて, TypeError を発生させる場合, 次の様にできます:

def prime?(n)
  raise TypeError, 'n must be Integer' unless n.instance_of? Integer
  return false if n < 0
  !/^(?:a?|(aa+?)\1+)$/.match?('a' * n)
end

prime? '2' rescue $!  # => #<TypeError: n must be Integer>

パフォーマンス

Ruby の正規表現を使って素数かどうかを確認する prime? メソッド, 実際, 素数の確認にかかる時間はどのくらいなのでしょう.

Ruby の標準ライブラリ benchmark を使って, その prime? メソッドと Prime::prime? メソッドとの処理時間の比較をしてみました:

def benchmark_prime_methods(n)
  Benchmark.benchmark(CAPTION, 16, FORMAT, ">quotient:") do |x|
    ta = x.report('prime?:')        { (0..n).each { |i| prime?       i } }
    tb = x.report('Prime::prime?:') { (0..n).each { |i| Prime.prime? i } }
    [ ta / tb ]
  end
end

benchmark_prime_methods 1_000
#                        user     system      total        real
# prime?:            0.039864   0.000412   0.040276 (  0.040302)
# Prime::prime?:     0.002337   0.000013   0.002350 (  0.002351)
# >quotient:        17.057766  31.692308        NaN ( 17.142493)

benchmark_prime_methods 10_000
#                        user     system      total        real
# prime?:           16.986404   0.021807  17.008211 ( 17.017431)
# Prime::prime?:     0.026538   0.001047   0.027585 (  0.027612)
# >quotient:       640.078529  20.828080        NaN (616.305628)