素数判定を正規表現と各種言語で比較してみた

始まり

SARAHでは2022年6月から幅広く技術で楽しむ機会を作るために、TechMeetupという名でエンジニアが集まっています。
第一回はシェル芸、第2回目は正規表現をやりました。

正規表現の回では、Regex Golfを全員で説いて回答を見せ合う会をやりました。
Regex Golfの中で素数判定を正規表現で書く問題があるのですが、なかなかおもしろいなと思いこの記事を書こうと思った次第です。

正規表現で素数判定できるんだ

はい、知りませんでした。
こんな感じで書けるらしい。(x文字数で判定）

^(?!(xx+)\1+$|^x$)

(xx+)でxx,xxx,xxxx,xxxxx…をグループ化
グループ化したものの1回以上の繰り返し（=倍数）の否定なので、素数がでるという感じらしい。
全く思いつかなかった。。

実用的なのか？

気になります。
各種言語の実装と正規表現で10秒間に何個ずつ判定できるのかやってみます。
スクリプトたち

Golang

func isPrimeGo(num int) bool {
	if num == 1 {
		return false
	}
	if num == 2 {
		return true
	}
	if num%2 == 0 {
		return false
	}
	root := int(math.Sqrt(float64(num)))
	for p := 3; p <= root+1; p += 2 {
		if num%p == 0 {
			return false
		}
	}
	return true
}

9791542 is not prime
9791543 is prime
9791544 is not prime

9791544

Golang/正規表現

const (
	count = 10000000
	char  = "x"
)

var re = pcre.MustCompile(fmt.Sprintf(`^(?!(%s%s+)\1+$|^%s$)`, char, char, char), 0)

func isPrimeRegex(num int) bool {
	chars := strings.Repeat(char, num)
	isPrime := re.Matcher([]byte(chars), 0).Matches()
	return isPrime
}

5322 is not prime
5323 is prime
5324 is not prime

5324

※PCRE使用

Ruby

def is_prime_ruby(num)
  return false if num == 1
  return true if num == 2 || num == 3
  return false if num % 2 == 0

  root = Math.sqrt(num).floor
  (3..(root + 1)).step(2).each do |p|
    if num % p == 0
      return false
    end
  end

  return true
end

1583840 is not prime
1583841 is not prime
1583842 is not prime

1583842

Ruby/正規表現

CHAR = "x"
PATTERN = Regexp.compile(/^(?!(#{CHAR}#{CHAR}+)\1+$|^#{CHAR}$)/)

def is_prime_regex(num)
  chars = CHAR * num
  return PATTERN.match?(chars)
end

7016 is not prime
7017 is not prime
7018 is not prime

7018

Python

def is_prime_python(num):
    if num == 1:
        return False
    if num == 2 or num == 3:
        return True
    if num % 2 == 0:
        return False

    root = math.floor(math.sqrt(num))
    for p in range(3, (root + 1), 2):
        if num % p == 0:
            return False

    return True

3009154 is not prime
3009155 is not prime
3009156 is not prime

3009156

Python/正規表現

COUNT = 100000000
CHAR = "x"
PATTERN = re.compile(f'^(?!({CHAR}{CHAR}+)\\1+$|^{CHAR}$)')

def is_prime_regex(num):
    chars = CHAR * num
    if bool(PATTERN.search(chars)):
        return True
    else:
        return False

6093 is not prime
6094 is not prime
6095 is not prime

6095

Zig(2022/8/17追記)

const std = @import("std");
const count = 100000000;

pub fn main() anyerror!void {
    var n:i64 = 1;
    while(n <= count) {
      var result: bool = isPrimeZig(n);
      if (result) {
        std.log.info("{} is prime", .{n});
      } else {
        std.log.info("{} is not prime", .{n});
      }
      n += 1;
    }
}

pub fn isPrimeZig(num: i64) bool {
  if (num == 1) return false;
  if (num == 2) return true;
  if (@rem(num, 2) == 0) return false;
  var root: f64 = @sqrt(@intToFloat(f64, num));
  var end: i64 = @floatToInt(i64, (root + 1));
  var p: i64 = 3;
  while(p <= end) {
    if (@rem(num, p) == 0) return false;
    p += 2;
  }
  return true;
}

info: 5601135 is not prime
info: 5601136 is not prime
info: 5601137 is not prime

5601137

Rust(2022/11/9追記)

use num::Float;

static COUNT: i64 = 100000000;

fn main() {
    for i in 1..COUNT {
        let result: bool = is_prime(i);
        if result {
            println!("{} is prime", i);
        } else {
            println!("{} is not prime", i);
        }
    }
}

pub fn is_prime(num: i64) -> bool {
    if num == 1 {
        return false;
    }
    if num == 2 {
        return true;
    }
    if num % 2 == 0 {
        return false;
    }
    let root: i64 = Float::sqrt(num as f64) as i64;
    for i in (3..root + 1).step_by(2) {
        if num % i == 0 {
            return false;
        }
    }
    return true;
}

6065153 is prime
6065154 is not prime
6065155 is not prime
6065156 is not prime
6065157 is not prime

6065157

まとめ

実装	判定個数
Golang	9791544
Golang/正規表現	5324
Ruby	1583842
Ruby/正規表現	7018
Python　3.10.4	2983800
Python　3.10.4/正規表現	6095
Python　3.11.0	3215272
Python　3.11.0/正規表現	6115
Zig	5601137
Rust	6065157

• 結論、素数判定は正規表現使わずに実装しよう！
  （個人的にはどこかで使いたい）
• やっぱりGoは早かった。
• AKS素数判定法/ミラーラビン素数判定法も試したい