Haskellで素数列生成 - ネギのメモ帳

練習がてら.

primes :: [Integer]
primes = 2:3:5:7: (filter isPrime xs)
  where xs = concat $ iterate (map (+10)) [11,13,17,19]

isPrime :: Integer -> Bool
isPrime n
  | n <=1 = False
isPrime n = and $ map ((==1) . (gcd n)) $ takeWhile (<=sqrt' n) primes

sqrt' :: Integer -> Integer
sqrt' = floor . sqrt . fromIntegral

isPrime

nが素数であるとは, $\sqrt n$ 以下の全ての素数(primes)に対して互いに素であるときを言う.

primes

2,3,5,7は素数であるとする. 1の位が1,3,7,9の数を候補とし, 素数(isPrimeが真となるもの)だけを残す.

雑感

1の位が1,3,7,9になる数だけの数列を生成するのにもっと速そうな方法はないものか.
(/=0) . (mod n) とgcdとは大差ない気がする.
takeWhile (\k -> k^2 <= n) primes するよりは各nに対してsqrtを1回だけ計算する方が速いはず.

実行速度

main関数はこんな感じで.

import System.Environment (getArgs)
import Data.Time (getCurrentTime, diffUTCTime)

main = do
  args <- getArgs
  time0 <- getCurrentTime
  let n = (read $ head args) in
      print $ primes !! (n-1)
  time1 <- getCurrentTime
  print $ time1 `diffUTCTime` time0

コンパイル(-O)してコマンドプロンプトで実行してみた結果：

n	n番目の素数	計算時間
1000	7919	0.002s
10000	104729	0.044s
100000	1299709	1.191s
1000000	15485863	34.449s
10000000	179424673	989.887s

環境：
GHC 7.8.3 on Haskell Platform 2014.2.0.0
Windows 7 Pro 64bit / Core i7-4770 3.40GHz / 16GB