« Project Euler : Problem 20 ~ 整数 ⇌ リスト | トップページ | 人のブログの間違いが気になって…… »

2010年4月24日 (土)

Project Euler : Problem 21 〜 友愛数

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

 

 「約数の和」は素因数分解の結果から簡単に出すことができます(詳しくは『数学ガール』をご覧ください)。

 前に投稿した記事にも書きましたが、一回だけ素因数分解を行う場合、Ruby などの通常の手続き型の言語であれば、素数を求める事自体にかなりのコストがかかるため、素数列を作ってから素因数分解を行うより、2 及び奇数で割り続けた方が速く結果が出ます。
 ところが今回のように大量の素因数分解を繰り返し行う場合は、あらかじめ素数列を作っておいた方が速いようです。ただし処理を開始する時点では必要な素数の上限が分からないため、通常のプログラム言語では、あらかじめ多めに素数列を求めておいて素因数分解を始めるといった、少し無駄な計算を行うことになるかもしれません。

 その点、Haskell は遅延評価で処理を行うので、その時点で必要になった分だけ素数を計算しますし、一度計算して得られた素数列は処理が終わるまでずっと保持されるので、無駄はありません。
 そこで、今回は素数を求めながら素因数分解を行うようにしました。

import Data.List(group) -- 素数列 primes :: Integral a => [a] primes = map fromIntegral ([2, 3] ++ primes' :: [Int]) where isPrime m (x : xs) | x * x > m = True | rem m x == 0 = False | otherwise = isPrime m xs primes' = 5 : sieve 1 sieve n = filter (`isPrime` primes') ns ++ sieve (n + 1000) where ns = [6 * x + y | x <- [n .. n + 999], y <- [1, 5]] -- 素因数分解 factorize :: Integral a => a -> [(a, Int)] factorize 1 = [(1, 0)] factorize n = format $ factorize' n primes where factorize' n ps@(p : ps') | p * p > n = [n] | rem n p == 0 = p : factorize' (div n p) ps | otherwise = factorize' n ps' format ps = [(x, length xs) | xs@(x : _) <- group ps] -- 真の約数の和 sumOfDivs :: Integral a => a -> a sumOfDivs 1 = 0 sumOfDivs n = product [calc f i | (f, i) <- factorize n] - n where calc f i = div (f ^ (i + 1) - 1) (f - 1) -- 友愛数のペアのうち、小さい値が引数の範囲内にあるものを返す。 -- ex : amicablePairs 2 1200 => [(220,284),(1184,1210)] amicablePairs :: Integral a => a -> a -> [(a, a)] amicablePairs from to = [(x, y) | x <- [from .. to], let y = sumOfDivs x, x < y, x == sumOfDivs y] problem021 :: Int problem021 = sum [a + b | (a, b) <- amicablePairs 2 10000] main = print problem021
 以前紹介した素数列を求める関数と素因数分解を行う関数ががんばってくれたおかげで、私のパソコン (Ubuntu 9.10, Pentium M, 1500MHz) では約 0.04 秒で答えが出ました。これは、この問題を Ruby 1.9 で解いたときの約 10 倍の速さです。

 コンパイルをするのが面倒くさいと思うこともたまにはありますが、比較的簡潔なコードでかなり速いコードが書けるので、私のようなアマチュアプログラマーには Haskell は非常に魅力的な言語です。

« Project Euler : Problem 20 ~ 整数 ⇌ リスト | トップページ | 人のブログの間違いが気になって…… »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 21 〜 友愛数:

« Project Euler : Problem 20 ~ 整数 ⇌ リスト | トップページ | 人のブログの間違いが気になって…… »

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

最近のトラックバック

無料ブログはココログ