« Project Euler : Problem 22 | トップページ | Project Euler : Problem 24 ~ 順列 »

2010年5月 8日 (土)

Project Euler : Problem 23 ~ 過剰数

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

 

 最初は、以前 Ruby でこの問題を解いた時と同じ方針でやってみたのですが、配列の更新に時間がかかるためか、答えが出るまでに 7 秒もかかってしまいました。

 そこで単純に、ある数から過剰数を小さい順に引いていって、過剰数にならないものだけを集めていくことにしました。
 ただし、何度も過剰数の判定を行う必要があるので、予め「インデックスが過剰数なら要素が "True"、そうでなければ要素が "False" になるような配列を準備しておきました。
 この方法だと、過剰数の判定に時間がかからないので、約 0.5 秒ほどで、答えが出ました。解法を変えるだけでここまで高速化したのには、びっくりしました。

import Data.Array -- 平方根の整数部分 isqrt :: Integral a => a -> a isqrt = truncate . sqrt . fromIntegral -- 真の約数の和 sumOfDivs :: Integral a => a -> a sumOfDivs 1 = 0 sumOfDivs n = sum ns1 + sum ns2' - n where ns1 = [x | x <- [1 .. isqrt n], rem n x == 0] ns2 = map (div n) ns1 ns2' = if last ns1 == last ns2 then init ns2 else ns2 -- 過剰数か ? isAbundant :: Integral a => a -> Bool isAbundant 1 = False isAbundant n = n < sumOfDivs n problem023 :: Int problem023 = sum $ filter notSum [1 .. limit] where limit = 28123 abuTest = listArray (1, limit) [isAbundant i | i <- [1 .. limit]] abuList = filter (abuTest !) [1 .. limit] notSum n = and [not $ abuTest ! (n - a) | a <- as] where as = takeWhile (<= div n 2) abuList main = print problem023
 「真の約数の和」は素因数分解の結果を利用して求める方法もあるのですが、今回は直接約数を求める方法にしました。

« Project Euler : Problem 22 | トップページ | Project Euler : Problem 24 ~ 順列 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 23 ~ 過剰数:

« Project Euler : Problem 22 | トップページ | Project Euler : Problem 24 ~ 順列 »

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

最近のトラックバック

無料ブログはココログ