・0 pv・2 min read
【素因数】一緒に考えませんか？ #Project Euler
考え方
素数型を作成
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ならではの素数生成法
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 primes6857
末筆ながら
ご意見求む!!
再帰を直接書くのは低級な行為だと教わったので、(効率を保ったまま)畳込みなどで書く方法が知りたいです
Haskellerさんへ
計算量, 見やすさ, 文化的な観点から見て改善点や他回答があればぜひお願いします！
スキル指標
実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください
読んだ本
- すごいH本
- 関数プログラミング実践入門 (途中)
つまり構文を知った程度で、関数型言語っぽい書き方を学び中です