--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2008/10/30

Project Euler: Problem 23

Problem 23

相当苦戦した。色々試すも、全て計算が終わらない。結局scheme による解答を見た。なるほど set をこのように使うのだな。

リンク先では sorted list による set を用いているが、本プログラムでは IntSet なるモジュールを使ってみた。ドキュメントの英語の意味が分からないのだけど、union や intersection に強いということなので。

実行結果

$ time ./23
4179871

real 0m35.947s
user 0m35.870s
sys 0m0.060s

プログラム

 1 import Data.IntSet (fromList,toList,union,insert,empty,fold)
 2
 3 divisors x = filter ((== 0. (mod x)) [1..(x `div` 2)]
 4
 5 abundants x = fromList $ filter isAbundant [1..x]
 6
 7 isAbundant x = x < (sum $ divisors x)
 8
 9 sumOfTwoAbundants n =
10   let abus = abundants n
11     in fold (\x acc -> union acc (f abus x)) empty abus
12   where f abus x = fold (\y acc' -> if x + y <= n
13                                       then insert (x+y) acc'
14                                       else acc')
15                         empty
16                         abus
17
18 fn = (sum [1..n]) - (sum' $ sumOfTwoAbundants n)
19   where n = 28123
20         sum' = fold (+0
21
22 main = print $ fn
スポンサーサイト

comment

post




上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。