« Project Euler : Problem 49 | トップページ | Project Euler : Problem 51 ~ 8個の素数 »

2010年10月14日 (木)

Project Euler : Problem 50

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 まず、問題にも書いてある 100 未満の場合で考えてみます。
 2 から始めて合計が 100 未満になる素数は [2,3,5,7,11,13,17,19] の 8 個になります。
 これらの数字から連続する部分を切り出し、合計を考えると

個数:(リスト, 合計) 8 個:([2,3,5,7,11,13,17,19], 77) 7 個:([2,3,5,7,11,13,17], 58), ([3,5,7,11,13,17,19], 75) 6 個:([2,3,5,7,11,13], 41), ([3,5,7,11,13,17], 56), ([5,7,11,13,17,19], 72) 5 個:([2,3,5,7,11], 28), ([3,5,7,11,13], 39), ([5,7,11,13,17], 53) ...
となっていきます。
 この中で 41 が初めて素数になるので、この場合の答えは 41 となります。

 この流れをそのままプログラミングしたのが次のコードです。

import ForEuler (primes, isPrime) -- ex : parts [1 .. 5] 3 => [[1,2,3],[2,3,4],[3,4,5]] parts :: [a] -> Int -> [[a]] parts xs n = take (length xs - n + 1) $ map (take n) $ iterate tail xs problem050 :: Int -> Int problem050 n = head $ filter isPrime $ map sum ps1 where ps1 = concatMap (parts ps2) $ reverse [1 .. length ps2] ps2 = take count primes count = length $ takeWhile (< n) primeSums where primeSums = tail $ scanl (+) 0 primes main :: IO () main = print $ problem050 1000000

« Project Euler : Problem 49 | トップページ | Project Euler : Problem 51 ~ 8個の素数 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 50:

« Project Euler : Problem 49 | トップページ | Project Euler : Problem 51 ~ 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            
フォト

最近のトラックバック

無料ブログはココログ