７問目

http://projecteuler.net/index.php?section=problems&id=7
10001番目の素数を求める。
素数を求めるアルゴリズムは色々あるみたいですが、とりあえず、既に分かっている素数で順に割って行ってどれでも割り切れなければ素数と判定する方法を採りました。
けっこう計算量が多くて時間がかかるので、

1. 2,3,5..と小さい素数で優先して割る（偶数や３の倍数という頻出する非素数を早くはねる）
2. nが素数かを判定するときは、（n以下ではなく） n^(1/2)以下の素数で割る

といったところに気を付けて、高速化を図っています。
そのおかげでこの問題は何とか解けたのですが、同じような１０問目がまだまだ遅くて困ってます。
そちらはまた後ほど。

main = print $ euler007 2 [] 10001

euler007 :: Int -> [Int] -> Int -> Int
euler007 x ps s
    | (s == 0) = last ps
    | (isPrime x ps) = euler007 (x + 1) (ps ++ [x]) (s - 1)
    | otherwise = euler007 (x + 1) ps s

isPrime :: Int -> [Int] -> Bool
isPrime x ps = all ((/= 0) . mod x) $
    takeWhile (<= (floor $ sqrt $ fromIntegral x)) ps

追記。１０問目の教訓から、少し速くなりました。

main = print $ primes !! 10000

primes :: [Int]
primes = 2 : filter isPrime [3..]

isPrime :: Int -> Bool
isPrime x = all ((/= 0) . mod x) $
    takeWhile (<= (floor $ sqrt $ fromIntegral x)) primes