【素因数】一緒に考えませんか？ #Project Euler

問3

600851475143の最大の素因数を求める

Project Euler ※解法の公開は問1～100のみ可

考え方

素数型を作成

type Primes = [Integer]

最大の素因数を求める

素数で順に割っていき、素因数だった場合は割って新しい値にしていくのが効率良さそう

solve :: Integer -> Primes -> Integer
solve n primes@(p:ps)
    | n < p^2 = n  
    | n `mod` p == 0 = solve (n `div` p)  primes 
    | otherwise = solve n ps 

素因数かどうかの判定は平方根までみれば良い

素数を作る (使えるならprimesモジュールの方が良い)

primes = sieve $ 2:[3,5..] -- 偶数は抜くというせめてものあがき
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

よくあるHaskellならではの素数生成法

末筆ながら

ご意見求む!!

再帰を直接書くのは低級な行為だと教わったので、(効率を保ったまま)畳込みなどで書く方法が知りたいです

Haskellerさんへ

計算量, 見やすさ, 文化的な観点から見て改善点や他回答があればぜひお願いします！

スキル指標

実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください

読んだ本

• すごいH本
• 関数プログラミング実践入門 (途中)

つまり構文を知った程度で、関数型言語っぽい書き方を学び中です