速い素数の求め方 - Life Goes Onちょっと前に haskell-cafe で速い素数の求め方が話題になっていました。 どんなもんだか確認した結果を記録。 僕がよく使ってたコードはこんな感じ。改めて見るとツッコミどころ満載です。 106 番目の素数を求めるのに手元のマシンで 2 分以上かかります。 primes0 = 2 : filter isPrime0 [3..] isPrime0 x = all ((/=0).mod x) $ takeWhile (<= (floor$sqrt$fromIntegral x)) primes0 平方根または二乗を求めるのに、いちいち整数から浮動小数に変換するのはコスト高すぎ 偶数も全てチェック対象にしているのは無駄 mod より rem の方が速い（これはなぜ？） というあたりを修正したのが↓のコード。1 分 20 秒。 primes1 = 2 : 3 : filter isPrime
