おいらのオイラー。
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.3～の奇数を、isPrime で素数かどうか判定する。
What is the 10 001st prime number?
Problem 7. 10001st prime
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10 001 番目の素数を求めよ.
Problem 7 「10001番目の素数」
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.愚直にやるとこうなった。
Problem 8. Largest product in a series
以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか.
Problem 8 「数字列中の最大の積」 (問題文に掲載されている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 と b と 1000 - a - b の組み合わせをリスト内包表記で作って、a^2 + b^2 = c^2For 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.
Problem 9. Special Pythagorean triplet
ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.
a^2 + b^2 = c^2例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である.
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.
Problem 9 「特別なピタゴラス数」
その組み合わせがピタゴラスの定理に当てはまるかどうかを検査する。
組み合わせを作ってから pythagorean' を再帰させるのではなくて、
組み合わせを作る段階で検査すればいいのでは、と思い書き直したのがこちら。
ぬおお…えらく短くなってくれた…！
(やっていることの分かりやすさはひょっとしたら9-1のほうが分かりやすいかもしれないけど…)
9-1, 9-2 ともに、ghci 上では1秒くらい、
最適化オプションつきでコンパイル後だとほぼ一瞬で実行が終わる。