素因数分解
inamori さんが Project Euler の解説記事で素因数分解について触れているのですが、そこで「あまりHaskellっぽくない」と書いてあるのが、気になってしまいました。
Haskell っぽいコードってどんなだろう、やっぱり自前で再帰せずに高階関数を使うのかな、そうするとこの場合は unfoldr だよな。とか考えながら書いたのが下のコード。
n の平方根以上の数では割らないようにするのがちょっと面倒でした。もっとすっきりした書き方があるでしょうか。
ちなみに、2以上のすべての数を素因数の候補にしていますが、もちろん 2と奇数だけでも、きちんとした素数列にしてもいいと思います。(性能差を確認できませんでした)
import Data.List main = print $ last $ factors 600851475143 factors :: Integer -> [Integer] factors n = unfoldr phi (n, takeWhile (\p -> p * p < n) [2..]) phi (1, _ ) = Nothing phi (n, ps) = case dropWhile (\p -> mod n p > 0) ps of [] -> Just (n, (1, [])) ps'@(p:_) -> Just (p, (div n p, ps'))