分割統治を使ってO(N*log N)になるそうな。 分割統治と聞いたら、反射的に平面を二分して〜 とここまでは誰も思う。と思う。 しかし、この後のマージの処理が説明を読んでも意味不明でした。

http://projecteuler.net/index.php?section=problems&id=70 ナイーブな方法。brute force 答えは出るが、遅い。これはよろしくない。 import Number import Data.List import Control.Arrow phi = product.map f.group.factors where f ps@(p:_) = let n = …

http://projecteuler.net/index.php?section=problems&id=69 n/Φ(n)をnの素因数で表現すれば、どれが最大かは自明。 つまり、nの素因数をとするとき import Number main = print.last.takeWhile(<1000000).scanl1(*)$primes

なかなか面白そうだ。 不確定状況下での意思決定とかに応用しようと思えばできそうではある。きれいに解けるかはまったく分からないが。

http://projecteuler.net/index.php?section=problems&id=74 いわゆる、すなおなアルゴリズム。 よって、遅い。 import Data.List import Data.Char next = toInteger.sum.map (f.digitToInt).(show::Integer->String) where f n = product [1..n] link = le…

http://projecteuler.net/index.php?section=problems&id=73 Problem 71とほぼ同じ import Data.List p073 d' =foldl1' (+) [1|d<-[4..d'],n<-[d`div`3+1..d`div`2],gcd n d==1] main = print.p073$10^4

前のオイラーのΦ関数を利用。 import Number import Data.List phi = product.map f.group.factors where f ps@(p:_) = let n = length ps in p^(n-1)*(p-1) p072 d = foldl1' (+) .map phi$ [2..d] main = print.p072$10^6

はじめは全生成して、ごにょごにょ だったけど 明らかに計算量が O(N^2) だった。 ちょっと頭を使った。 import Data.List import Data.Ratio p071 d' = foldl1' max [n%d|d<-[2..d']\\[7],let n = 3*d `div` 7,gcd n d ==1] main = print.numerator.p071$10…