👋
素数判定を正規表現と各種言語で比較してみた
始まり
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素数判定法/ミラーラビン素数判定法も試したい
SARAHでは一皿に特化したごはん情報の投稿・配信・収集・解析するサービスをtoC,toBと多角的に展開しています。アプリ / Web / SaaS / データサイエンス を最新の環境と技術で広く運用します。 技術スタック詳細はこちら→ stackshare.io/companies/sarah-inc
Discussion