HaskellでProject Euler(Problem 1～3)

Haskell でプロジェクトオイラーに挑んでみる。おいら頑張るよ。
きっとおいらの数学力や Haskell 力が低いせいだろうけど、
何だかロジックは正しいはずだけど値を大きくすると処理時間がクソ遅いから
速くなるよう部分的に書き直すことに苦労した印象が。

Problem 1. Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Problem 1. Multiples of 3 and 5
10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.
同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.
Problem 1 「3と5の倍数」

少し汎用性を持たせたつもりで、何の倍数かも渡せるようにしてみた。
リスト内包表記で muls に渡した値のいずれかで割り切れる値のみのリストを作り、foldl1 で畳み込む。
もっといいやり方があるかもしれないけど、あまり悩まずすんなり解けた、かな。

Problem 2. Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Problem 2. Even Fibonacci numbers
フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万より小さい, 偶数値の項の総和を求めよ.
Problem 2 「偶数のフィボナッチ数」

まず、そもそもフィボナッチ数列を求める関数を作るのに苦労した。
はじめ何も考えずに

fib 0 = 1
fib 1 = 2
fib n = fib (n-2) + fib (n-1)

としていたが、これだと数が大きくなりにつれ遅くなり、400万はとてもじゃないけど無理そうだった。
一旦諦めてHaskellのフィボナッチ数列生成関数をフィボナッチ数列 - Haskell はスケるよなどを参考にしたコピペ版がこちら。

期待通り動いてくれてはいるが、これは自力では思いつかなそう。
何とか自分で考えて書いたバージョンがこちら。

fibList 関数を再帰的に呼び出して、逆順のフィボナッチ数列のリストを作っている。
リストの先頭2要素(fstElem,sndElem)を足して次項の値を求めて、それをリストの先頭に足していく。
引数のパターンマッチで、リストの先頭要素・第二要素・リスト全体を使いたかったのでasパターンを用いている。
作られたリストの先頭を取ると、その項のフィボナッチ数となる。
実行はほぼ一瞬で完了する。

Problem 3. Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Problem 3. Largest prime factor
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
Problem 3 「最大の素因数」

少し考えたけどものすごく時間がかかるものしか書けなかった…ので
検索して見つけた高速な因数分解を使用したバージョンをまず書いてみた。
(まず書いてみたも何も、ほぼコピペだけど…)

もう少し考えて自力で書いたバージョンがこちら。

primeFactors 関数を再帰的に呼び出している。
nが目的の値、mが2から始めてnまで再帰呼び出し中にインクリメントする値、listが素因数のリスト。
isPrimeFactor 関数で素因数かどうかを検査する。
mがすでに追加されている素因数のリストのいずれでも割り切れず、
nを割り切れる値なら素因数としている。
最初、8行目を「isPrimeFactor = primeFactors n (m + 1) (m:list)」と
nの値を変化させずに再帰呼び出しするようにしていたが、
それでは処理が非常に遅く(2から600851475143まで1ずつインクリメントして全ての値を検査しないと再帰終了条件とならない)
euler3-1.hsからヒントを得てmが素因数なら n / m の値を新しいnとして
再帰呼び出しするようにしてみた。