« Project Euler : Problem 9 〜 ピタゴラス数 | トップページ | Project Euler : Problem 11 »

2009年12月27日 (日)

Project Euler : Problem 10 〜 200万以下の素数の和

 問題はこちらをご覧ください。

 

 問題の解答の説明に入る前に、以前の記事の補足から……。
 "Haskell で素数"の記事に rst76 さんが付けてくださったコメントにもあるように、primes の型を [Int] にするとかなり速度が上がることが分かりました。
 Project Euler の問題を解くだけであれば、必要となる素数は Int の範囲で充分だとは思いますが、今回の問題のように最終的な解答が Int の範囲を越えることはありえます。型が [Int] のままでは over flow によって足元をすくわれてしまうこともありそうです。
 そこでまず intPrimes :: [Int] で [Int] 型の素数列を求めて、それを [Integer] に変換する事で primes :: [Integer] を求めることにしてみました。

 では、問題の解答です。

intPrimes :: [Int] intPrimes = [2, 3] ++ sieve [] (tail intPrimes) 5 where sieve divs (x : xs) n = ps ++ sieve (divs ++ [x]) xs (x * x + 2) where isPrime (y : ys) m | rem m y /= 0 = isPrime ys m | otherwise = False isPrime _ _ = True ps = filter (isPrime divs) [n, n + 2 .. x * x - 2] primes :: [Integer] primes = map fromIntegral intPrimes problem010 :: Integer problem010 = sum $ takeWhile (<= 2000000) primes main = print problem010
 Core Solo T1300 1.66GHz(2MB) のパソコンで約 0.67 秒で答えが出ました。primes :: [Integer] の時には約 1.5 秒かかっていたので、型を変えただけでかなりの高速化になっています。

 「エラトステネスの篩」の条件限定版も、素数を生成する時の型を [Int] にするとやはり高速化できます。

primeList :: Int -> [Integer] primeList n = map fromIntegral $ 2 : sieve [3, 5 .. n] where isqrt = (truncate . sqrt . fromIntegral) n sieve (p : xs) | p > isqrt = p : xs | otherwise = p : sieve [x | x <- xs, rem x p /= 0] main = print $ sum $ primeList 2000000
 Core Solo T1300 1.66GHz(2MB) のパソコンで約 1.38 秒で答えが出ました。

 Ruby や Scheme を使っている時には「型」について悩むことはありませんでしたが、Haskell では「型」についてもっとしっかり考えていく必要があるようです。

« Project Euler : Problem 9 〜 ピタゴラス数 | トップページ | Project Euler : Problem 11 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/47132320

この記事へのトラックバック一覧です: Project Euler : Problem 10 〜 200万以下の素数の和:

« Project Euler : Problem 9 〜 ピタゴラス数 | トップページ | Project Euler : Problem 11 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ