Life Goes On

まあまあだけど楽しんでる方です

素因数分解

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'))