« Haskell で素数 | トップページ | Project Euler : Problem 8 »

2009年12月25日 (金)

Project Euler : Problem 7 ~ 10001 番目の素数

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

 

 前回の記事に出てきた素数列を作る関数を使います。

 まずは「エラトステネスの篩」から。

primes :: [Integer] primes = 2 : sieve [3, 5 ..] where sieve (x : xs) = x : sieve [y | y <- xs, rem y x /= 0] main = print $ primes !! 10000
 約 6.1 秒と、ちょっと時間がかかります。

 

 次に、自分が改良した関数。

primes :: [Integer] primes = [2, 3] ++ sieve [] (tail primes) 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] main = print $ primes !! 10000
 約 0.05 秒で答えが出ます。「エラトステネスの篩」の約 120 倍のスピードです。

« Haskell で素数 | トップページ | Project Euler : Problem 8 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 7 ~ 10001 番目の素数:

» Project Euler : Problem 10 〜 200万以下の素数の和 [ツムジのひとりごと]
 問題はこちらをご覧ください。    問題の解答の説明に入る前に、以前の記事の補足から……。  "Haskell で素数"の記事に rst76 さんが付けてくださったコメントにもあるように、primes の型を [Int] にするとかなり速度が上がることが分かりました。  Pro... [続きを読む]

« Haskell で素数 | トップページ | Project Euler : Problem 8 »

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            
フォト

最近のトラックバック

無料ブログはココログ