素数探索@Ruby

キミならどう書く 2.0 - ROUND 1 -にて、「100までの整数から素数を列挙せよ」とのお題。

(2..100).select{|i|(2...i).all?{|j|i%j!=0}}

とりあえず効率無視で短さ重視。

(2..100).select{|i|/^(11+)\1+$/!~'1'*i}

と思ったら、perl - 100までの素数 にある正規表現を使った手法を Ruby に移植した方が短い罠。参考までに、正規表現で素因数分解するを。

[2]+(3..100).select{|i|2**(i-1)%i==1}

フェルマーテスト を使った詐欺くさい方法で最短記録更新(ぉ 最初の擬素数 341 が登場するまでは正しい素数列を得られます。

Miller-Rabin テストや AKS アルゴリズムのものも誰か書いてくれるんだろうな、と期待しよう。