Problem 70

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 = length ps
                       in p^(n-1)*(p-1)
nPhi = product.map f.nub.factors
    where f = (\x-> x / (x-1)).fromInteger
p070 n = snd.minimum.map (nPhi&&&id).filter f $[2..n]
    where f x =(sort.show) x == (sort.show.phi)x
main = print.p070$9999999

それで改良。このアルゴリズムには注意が必要だ。
前提:最適な値は二つの素数の積で表現できる。
を根拠もなしに使っている。直感的には納得できるが…
必ず、二つの素数の積になるとはだれも保証はないがこの問題に限っては前提を満たす。
何でかって?それは一回ナイーブな方法で解を求めているから。なんて卑怯な。

p n =[(f p q,p*q)|p<-ps,q<-qs p,(sort.show)(p*q)==(sort.show)((p-1)*(q-1))]
    where n'=floor.sqrt.fromInteger$n
          ps = reverse.takeWhile(<=n')$primes
          qs p= reverse.takeWhile(<=(n`div`p))$primes
          f p q = let (p',q')=(fromInteger p,fromInteger q)
                  in p'*q'/((p'-1)*(q'-1))

main = print.snd.minimum.p$9999999

こういう場当たり的なものは好きじゃない。
10倍ぐらい速くなったのは事実ではあるが…