HaskellでProject Euler(Problem 7～9) - ザネリは列車を見送った

Problem 7. 10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
最初の6個の素数は 2, 3, 5, 7, 11, 13 であり、6番目の素数は13だということが分かる。
10001番目の素数を求めよ。

3～の奇数を、isPrime で素数かどうか判定する。
isPrime はすでに素数として判定された list の中の検査する値の
平方根以下の値で割り切れるかどうかを検査している。
はじめに prime' 3 [] ではなくて prime' 3 [2] と素数のリストにあらかじめ 2 を入れておいて
length list >= n = list で終わらせることも考えたが、
m が奇数のみであるのに isPrime で m `mod` 2 /= 0 も実行するのは無駄かなぁ、と思い、
n=1 の場合のみ特別扱いとした。
最適化オプション「-O」をつけてコンパイルして5秒くらい…。
もう少し速くならないものかとしてみたものがこちら。

すでに検査済みの素数の最大値側から順に割り切れるか検査するより
最小値側から順に検査したほうが割り切れる値が見つかるのが早いと思い、
素数のリストを保持する list と、他の素数で割り切れるか検査するための list' を分けてみた。
list は降順、list' は昇順。
これは速い。ghci 上でも2秒くらい、最適化オプションをつけてコンパイルすると1秒くらい。
うーん…しかし見るからに無駄そうな処理をしていて、本当にこれでいいものやら。
list'++[m] も要素数が大きくなれば遅くなるように思うんだけどな。

Problem 8. Largest product in a series

Find the greatest product of five consecutive digits in the 1000-digit number.
以下の1000桁の数字の中の5つの連続する数の積の最大値を求めよ。
(問題文に掲載されている1000桁の数字は省略)

愚直にやるとこうなった。
1000桁の数字を文字列にし、最初の5文字を1文字ずつ数値化して掛けた値と
現在保持している最大値の大きいほうを選んで再帰する。
any (== '0') num はやってもやらなくても実行時間に差が見られなかったけど、
5つの数字の中に0が含まれていれば積は必ず0になるので
積を求めて現在の最大値と比較する処理を省くために入れてみた。

Problem 9. Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
ピタゴラスの三項とは、a < b < c のとき、
a^2 + b^2 = c^2 を満たす3つの自然数の組み合わせである。
例えば 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である。
a + b + c = 1000 を満たすピタゴラスの三項がちょうど一つだけ存在する。
abc の積を求めよ。

とりうる a と b と 1000 - a - b の組み合わせをリスト内包表記で作って、
その組み合わせがピタゴラスの定理に当てはまるかどうかを検査する。
組み合わせを作ってから pythagorean' を再帰させるのではなくて、
組み合わせを作る段階で検査すればいいのでは、と思い書き直したのがこちら。

ぬおお…えらく短くなってくれた…！
(やっていることの分かりやすさはひょっとしたら9-1のほうが分かりやすいかもしれないけど…)
9-1, 9-2 ともに、ghci 上では1秒くらい、
最適化オプションつきでコンパイル後だとほぼ一瞬で実行が終わる。