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倍ぐらい速くなったのは事実ではあるが…

コンテンツ