http://projecteuler.net/index.php?section=problems&id=3
素因数分解するので、まず素数列を出さなければならない、ということはもちろんなくて、ここでは2, 3, 5, 7, 9, …と割っていくことにする。
prime_candidates = 2:[ 3, 5.. ]
これで、所望の無限リストが得られる。詳しく説明すると、
[ 1.. ]
で、1, 2, 3, …という無限リストが得られる。
[ 1, 3.. ]
これで、1が初項で公差が2の無限リストが得られる。最初の2:は、無限リストの頭に2がくっついたくらいに思っておけばよいようだ。
あとは2から順に割っていき、割り切れたら割った数をまた同じ素数で割る。割り切れなかったら、次の素数候補で割る。素数候補の自乗より大きければ残った数が最後の素数になる。これを再帰で表現する。
prime_candidates = 2:[ 3, 5.. ]
factorize 1 (p:primes) = []
factorize n (p:primes) =
if p * p > n then [ n ]
else if (mod n p) == 0 then (factorize (div n p) (p:primes)) ++ [ p ]
else factorize n primes
n = 600851475143
f = factorize n prime_candidates
main = print (head f)
あまりHaskellっぽくないコードのような気が。
factorize 1 (p:primes) = []
factorize n (p:primes) = …
のところは、最初の引数が1のときだけ上の定義になって、その他のときは下になる。数学で漸化式をこう書くみたいな感じ？
a1 = 1
an+1 = 2an + 1
あるいは、C++のTemplateみたい。
if 〜 else 〜は上のように書く。適当にインデントしないといけないみたい。
(p:primes)
のところは、引数のリストが分解されるような感じになって、pがリストの頭の要素で、primesが残りになる。
mod n p
div n p
は整数の割り算。
n / p
は実数の割り算になってしまう。
これで、factorizeは素因数を逆から順に並べたリストになるので、その頭を取り出せば最大の素因数になる。
最初から最大の素因数だけ求めるのならこんな感じか？
prime_candidates = 2:[ 3, 5.. ]
max_factor n (p:primes) =
if p * p > n then n
else if p == n then n
else if (mod n p) == 0 then max_factor (div n p) (p:primes)
else max_factor n primes
n = 600851475143
main = print (max_factor n prime_candidates)
最初のコードをPythonで書くと、無限リストはジェネレータで表せばよいから、
def prime_candidates():
yield 2
n = 3
while True:
yield n
n += 2def factorize(n, p, g):
if n == 1:
return []
elif p * p > n:
return [ n ]
elif n % p == 0:
return factorize(n / p, p, g) + [ p ]
else:
return factorize(n, g.next(), g)N = 600851475143
g = prime_candidates()
f = factorize(N, g.next(), g)
print f[0]
