« Project Euler : Problem 26 ~ 循環節の長さ | トップページ | Project Euler : Problem 28 »

2010年6月 1日 (火)

Project Euler : Problem 27 ~ 関数をデータとして扱う

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

 

 愚直にやると、 3996001 通りの二次式について調べることになるので、ちょっと大変です。そこで a と b の範囲を絞っていきます。

 以下の文章では、 v = n² + an + b として話を進めます。

 まず、 b について考えます。
 b が偶数の場合、 n が 2 以上の偶数の場合に v も偶数になってしまうので、 b が偶数の場合は除外しても良さそうです。
 また、n = 0 の時、 v = b が素数になるためには、 b は素数でなければなりません。
 従って b は「1000 未満の奇素数」の範囲で考えれば良さそうです。

 次に、 a について考えます。
 n = 1 の時、v は素数なので v = 1 + a + b > 1 と考えられます。このことから a > -b という関係が分かります。また、 b は奇素数なので、 a が偶数だと、 v も偶数になってしまうので、 a は奇数でなければなりません。
 従って a は「-b より大きく、1000 未満の奇数」ということになります。

 これで調べる二次式は 121646 通りまで絞り込めました。

 実際のコードですが、今回は 2 パターン考えてみました。
 まずは、ほとんどの人考えたであろうアプローチで、実際に二次式の n に 0 から順に整数を当てはめていき、素数が何個できるかを調べる方法です。

import Data.List (maximumBy) import Data.Ord (comparing) divs :: Integral a => [a] divs = 2 : 3 : [x + y | x <- [6, 12 ..], y <- [-1, 1]] -- 素数判定 : 簡易版 isPrime :: Integral a => a -> Bool isPrime n = (n > 1) && iter divs where iter (x : xs) | x * x > n = True | rem n x == 0 = False | otherwise = iter xs primeCount :: Int -> Int -> Int primeCount a b = head $ dropWhile check [0 ..] where check n = isPrime (n * n + a * n + b) problem027 :: Int problem027 = a * b where (a, b, _) = maximumBy comp xs comp (_, _, x) (_, _, y) = compare x y xs = [(a, b, primeCount a b) | b <- bs, a <- [-b, -b + 2 .. 999]] bs = filter isPrime [3, 5 .. 1000] main = print problem027

 

 もう一つの方法は、せっかく Haskell を使っているのだから、関数をデータとして扱ってみようかと……。
 具体的には、関数 f を "f a b n = n * n + a * n + b" と定義しておき、「f に a と b を部分適用した関数」、 a 、 b をタプルにまとめたものを要素としたリスト "funcs" を準備します。
 そして、「f に a と b を部分適用した関数」に 0 から順に整数を適用していき、「f に a と b を部分適用した関数」が素数になったものだけを残していく、という操作を繰り替えして、最後にリストの要素が一つになった時点で a と b を取り出しました。

divs :: Integral a => [a] divs = 2 : 3 : [x + y | x <- [6, 12 ..], y <- [-1, 1]] -- 素数判定 : 簡易版 isPrime :: Integral a => a -> Bool isPrime n = (n > 1) && iter divs where iter (x : xs) | x * x > n = True | rem n x == 0 = False | otherwise = iter xs funcs :: [(Int -> Int, Int, Int)] funcs = [(f a b, a, b) | b <- bs, a <- [-b, -b + 2 .. 999]] where f a b n = n * n + a * n + b bs = filter isPrime [3, 5 .. 1000] problem027 :: Int problem027 = iter funcs [0 ..] where iter [(_, a, b)] _ = a * b iter xs (n : ns) = iter xs' ns where xs' = [x | x@(f, _, _) <- xs, isPrime (f n)] main = print problem027

 a と b の範囲を絞り込んだおかげで、コンパイルしたコードではどちらも約 0.1 秒で答えが出ます。
 自分としては、「関数」をデータとして扱う 2 つ目のコードが関数型言語の Haskell らしくて好きです。

« Project Euler : Problem 26 ~ 循環節の長さ | トップページ | Project Euler : Problem 28 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 27 ~ 関数をデータとして扱う:

« Project Euler : Problem 26 ~ 循環節の長さ | トップページ | Project Euler : Problem 28 »

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

最近のトラックバック

無料ブログはココログ