Magicode logo
Magicode
2 min read

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

https://cdn.apollon.ai/media/notebox/348f3dcc-08c7-45fb-bffe-f71bfca7c870.jpeg

問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ならではの素数生成法
haskell
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
primes = sieve $ 2:[3,5..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

print $ solve 600851475143 primes

6857

末筆ながら

ご意見求む!!

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

Haskellerさんへ

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

スキル指標

実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください
読んだ本
  • すごいH本
  • 関数プログラミング実践入門 (途中)
つまり構文を知った程度で、関数型言語っぽい書き方を学び中です

Discussion

コメントにはログインが必要です。