カテゴリー: Project Euler

三角数の数列は自然数の和で生成することができる。したがって7番目の三角数 は1+2+3+4+5+6+7=28である。三角数の最初の10項は 1,3,6,10,15,21,28,36,45,55,…となる。

最初の7つの三角数の約数を列挙すると以下のようになる。
1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28

ここで、7番目の三角数である28が約数の数が5を超える最初の三角数であるこ とがわかる。約数の数が500より大きくなる最初の三角数を求めよ。

まず無限に続く三角数のリストを以下のように定義する。いろいろな書き方が できると思うが、n番目の三角数はn-1番目の三角数にnを足したものであるとい う考えでzipWithを使って定義している。次に全ての約数のリストを求める関数 factorsを定義する。1から順番に割り切れるか試している。割り切れた場合に はその数と商が約数となる。呼び出すときに余計な初期値を指定しなくてもい いようにfactorsを定義し、実際の処理はローカル関数のfactors’で行っている。

三角数のリストにmapでfactorsを適用し約数のリストのリストを求める。そし てfilterを使用して、その中から約数のリストの長さが500より大きいものをと りだし、headで最初のものを求める。求まった約数のリストの最後尾をlastで 取り出し解として表示する。アドホックであるが、約数の中で一番最後のもの が三角数そのものであることを利用している。

triangles = zipWith (+) [1..] (0 : triangles)

factors n = factors' n 1 []
    where factors' n x l
              | x * x > n      = l
              | x * x == n     = x : l
              | n `mod` x == 0 = x : factors' n (x + 1) ((n `div` x) : l)
              | otherwise      = factors' n (x + 1) l

euler012 = last $ head $ filter (\x -> length x > 500) $ map factors triangles

以下の20×20の格子状にならんだ数字のうち、対角線上に並んだ4つの数字が赤 く色がついている。

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

この4つの数の積は26x63x78x14=1788696である。

この20×20の格子状で、縦横斜めのいずれかの方向に並んだ4つの数字の積の最 大値を求めよ。

ここで再びデータの扱いが問題となる。今回も数が少ないのでプログラム中に リテラルとして埋め込むことにする。問題を素直に実装する場合、データへの ランダムアクセスが必要となるが、基本的にはリストというのはランダムアク セスに適していない。そこでHaskellの配列を使うことにする。

まずデータは都合のいい形に書き換えることにする。今回は以下のように問題 のデータにガード用の0を追加したリストとした。そしてlistArray関数を使い 配列を生成する。配列のインデックスは任意の値が指定できる。今回は本来の データが(0,0)-(19,19)の範囲にくるように、(0, -3)から(22, 22)の範囲をイ ンデックスに指定した。

続いて問題を解くプログラムであるが、全ての場所を起点にして縦横斜めの4つ の積をそれぞれ求めてリストにしmaximumで最大値を求めるというものである。 ここでproduct4はある点での縦横斜め4方向の積のリストを求める関数。リスト の内包表記で全ての点の積のリストを求めている。product4は実際には product4’を計算する方向を指定して呼び出し結果をリストにしている。 product4’では配列から方向に従って4つの値を取り出したリストを生成し、 productでその積を求めている。配列の要素にアクセスする演算は!である。

euler011Grid = listArray ((0, -3), (22, 22))
  [0,0,0,08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08,0,0,0,
  0,0,0,49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00,0,0,0,
  0,0,0,81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65,0,0,0,
  0,0,0,52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91,0,0,0,
  0,0,0,22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80,0,0,0,
  0,0,0,24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50,0,0,0,
  0,0,0,32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70,0,0,0,
  0,0,0,67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21,0,0,0,
  0,0,0,24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72,0,0,0,
  0,0,0,21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95,0,0,0,
  0,0,0,78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92,0,0,0,
  0,0,0,16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57,0,0,0,
  0,0,0,86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58,0,0,0,
  0,0,0,19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40,0,0,0,
  0,0,0,04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66,0,0,0,
  0,0,0,88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69,0,0,0,
  0,0,0,04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36,0,0,0,
  0,0,0,20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16,0,0,0,
  0,0,0,20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54,0,0,0,
  0,0,0,01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

euler011 = maximum [ maximum $ product4 i j | i 

10未満の素数の和は2+3+5+7=17である。

200万未満の素数の和を求めよ。

問題自体は単なる計算問題である。しかし、ここまでくると問題2の定義では素 数の計算が遅すぎてどうしようもなくなってくる。ここで少しだけ素数の計算 の高速化を考える。まずはエラトステネスの篩のアルゴリズムを振り返ってみ る。2が素数なので2以上の数のうち2の倍数を除外する。このとき3は除外され てないので素数である。次に3が素数なので3以上の数のうち3の倍数を除外する。 4は2の倍数で除外されているが5は除外されていないので素数である。次に5の 倍数をという風に素数の倍数をふるい落とすことで残った数が全て素数になる というのがアルゴリズムの大まかな説明となる。

このアルゴリズムは素数を求めたい対象となる数の上限があらかじめ決まって いて、例えばそのbit配列に対して、既に求まった素数の倍数にあたる部分を チェックしていくような実装にした場合非常に高速である。

ここでHaskellで実行を考える。Haskellでは素数が無限のリストとして表され るが、当然無限のリストから2の倍数を全て除外することはできない。したがっ て実際には必要に応じて2の倍数なら除外する関数のようなものを内部的に生成 することになる。3の場合や5の場合も同様である。こういった後で計算するた めの内部的な構造のことはthunkと呼ばれている。

ここで実際にn番目の素数の値を使う場面を考えてみると、n-1番目までの素数 の倍数かどうかを試すthunk を全て実行して素数かどうかの判定をすることに なる。やっている処理自体は不自然ではない。n番目の素数というのはn-1番目 までのどの素数の倍数にもなっていないものである。しかし、それがエラトス テネスの篩的に実装されているためにn-1番目までの素数の倍数かどうかのチェッ クがそれぞれの別々のthunk になっているのは大きなオーバーヘッドである。

ここで、実際の処理を素直に表現したような書き方で素数primesを書き直す。 候補となる数列に対して素数かどうかのチェックをする関数isPrimeをfilterで 適用する。これによって少なくとも一つの素数のチェックに必要な関数適用は 一つに減らすことができる。また倍数かどうかのチェックもひとつ前の素数ま でではなく、nの平方根以下の素数までのチェックにできる。すべての素数で割 り切れないことのチェックはall関数を用いて以下のようにかける。

primes = 2 : filter isPrime [3, 5..]
    where isPrime n = all (\x -> n `mod` x /= 0)
                      $ takeWhile (\x -> x * x <= n) primes

euler010 = sum $ takeWhile (<= 2000000) primes

ピタゴラスの定理を満たす3つの整数の組とは、a<b<cでa^2+b^2=c^2を満 たすものである。

例えば、3^2+4^2=9+16=25=5^2である。

この条件を満たす3つの数字a,b,cのうちa+b+c=1000が成り立つものがちょうど 一つ存在する。その3つの数の積abcを求めよ。

この問題はプログラムを書かなくても数学的に手で解ける問題かもしれないが、 ここではプログラムで答えを求める。a,b,cに考えられる全ての組み合わせを順 に試していくプログラムを書くと以下のようになる。ただし、実行速度の問題 もあるので自明な部分は計算しない。まずa+b+c=1000なのでc=1000-a-bとあら わせる。aeuler009 = [a * b * (1000 – a – b) | a <- [1..333], b <- [a..((1000 – a) `div` 2)], a ^ 2 + b ^ 2 == (1000 – a – b) ^ 2]

次の1000文字の数字の中の連続した5つの数の積で最大のものを求めよ。

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

まずデータをどう扱うかというのが問題になる。演習的な問題では素数のよう にデータの扱いを気にしなくていいようなものが多いが、そういう意味でこの 問題は若干現実的な問題といえる。ただし、ここではデータ量が1000文字と少 ないのでプログラム中にリテラルで記述することにする。Haskellでは文字列は 文字のリストなので、リスト連結演算++で文字列をつなげることができる。 1000文字のデータは以下のeuler008Digitsのようになる。

次にプログラムを考える。まず文字列が1000個の文字のリストとして扱えるの でmapとdigitToIntを使って文字を数字に変換し、整数のリストとする。ここで その整数のリストに対して先頭から5個ずつの積を求める関数product5を適用し、 最後にその積の最大値を求める。

euler008Digits =
    "73167176531330624919225119674426574742355349194934" ++
    "96983520312774506326239578318016984801869478851843" ++
    "85861560789112949495459501737958331952853208805511" ++
    "12540698747158523863050715693290963295227443043557" ++
    "66896648950445244523161731856403098711121722383113" ++
    "62229893423380308135336276614282806444486645238749" ++
    "30358907296290491560440772390713810515859307960866" ++
    "70172427121883998797908792274921901699720888093776" ++
    "65727333001053367881220235421809751254540594752243" ++
    "52584907711670556013604839586446706324415722155397" ++
    "53697817977846174064955149290862569321978468622482" ++
    "83972241375657056057490261407972968652414535100474" ++
    "82166370484403199890008895243450658541227588666881" ++
    "16427171479924442928230863465674813919123162824586" ++
    "17866458359124566529476545682848912883142607690042" ++
    "24219022671055626321111109370544217506941658960408" ++
    "07198403850962455444362981230987879927244284909188" ++
    "84580156166097919133875499200524063689912560717606" ++
    "05886116467109405077541002256983155200055935729725" ++
    "71636269561882670428252483600823257530420752963450"

euler008 = maximum $ product5 $ map digitToInt euler008Digits
    where product5 (x1:x2:x3:x4:[])    = []
          product5 (x1:x2:x3:x4:x5:xs) =
              x1 * x2 * x3 * x4 * x5 : product5 (x2:x3:x4:x5:xs)

最初の6つの素数を列挙すると2,3,5,7,11,13となるので、6番目の素数は13であ ることがわかる。

10001番目の素数を求めよ。

この問題もわりと簡単な計算問題である。問題2で使用した素数の定義を使うこ とにする。リストのn番目の要素を返す関数は!!である。先頭の要素は0番目な ので10001番目の要素を求めるのは以下のようなプログラムになる。

euler007 = primes !! 10000

ただしこのプログラムは若干遅い。環境によっては実行が長すぎて気になるか もしれない。原因は素数を求めるコードが遅いからだ。ここでは本質的な問題 は棚上げにして別の方法を考える。ghcにはインタプリタのghciとコンパイラの ghcがあるが、コンパイルすることで若干実行速度を改善することができる。コ ンパイルした場合main関数が実行されることになるので問題7を解くプログラム は以下のように書ける。

sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]
primes = sieve $ 2 : [3, 5 ..]
euler007 = primes !! 10000
main = putStrLn $ show euler007

ここでshowは渡された値を文字列に変換する関数、putStrLnは文字列を画面に 表示する関数である。インタプリタが暗黙のうちに行っている処理に相当する 部分である。このコードが書かれたファイルをeuler007.hsとして以下のように コンパイルすることができる。今回はこれで実行時間の問題は解決されたこと にしよう。

[hoge@huga foo]$ ghc -O3 -o euler007 euler007.hs

最初の10個の自然数の2乗の和は1^2+2^2+…+10^2=385である。

最初の10個の自然数の和の2乗は(1+2+…+10)^2=55^2=3025である。

したがって、2乗の和と和の2乗の差は3025-385=2640となる。

最初の100個の自然数の2乗の和と和の2乗の差を求めよ。

この問題は単なる計算問題である。Haskellでは以下のようにかける。

euler006 = sum [1..100] ^ 2 - sum [x ^ 2 | x <- [1..100]]

2520は1から10までの全ての数で割り切れる最小の数である。 1から20までの全ての数で割り切れる最小の数を求めよ。

問題文にそって考えていく。割り切れるということは答えの数の素因数には1か ら20の数の素因数が全て含まれている。また求めるのは最小の数ということで 答えの数には必要最低限しか素因数が含まれていない。よって1から20の数を全 て素因数分解し、必要な素因数の積を求めることで答えが求まることがわかる。

まず1から20までのリストを生成する。次に問題3で定義したprimeFactorizeを 用いて素因数のリストを求める。map関数はリストの全ての要素に指定した関数 を適用する関数である。map関数を用いてprimeFactorizeを適用するが、 primeFactorizeでは対象となる数を1番目の引数に、素数のリストを2番目の引 数に渡す必要がある。

ここでHaskell風のやり方としては、まずflip関数を用いてprimeFactorizeの引 数の順序を入れ替えることができる。次に変化しない引数である素数のリスト を先に渡してしまうことができる（関数の部分適用）。これをmapで適用するこ とで、1から20の数の素因数を求めることが出来る。なれてないと若干読みづら いかもしれない。同じ操作を無名関数を用いて書くとmap (\x -> primeFactorize x primes) [1..20]という風にかける。

リストの全ての要素の積はproduct関数で求められる。必要最低限の素因数を求 める部分はローカル関数mergeで定義する。whereという構文はその文で使って いる変数をローカルに定義できる。数学的な文章をイメージするとわかりやす い。例えばここではeuler005という関数でmergeというものを使用し、次に where構文を用いてmergeの内容を定義している。

関数の定義自体はパターンマッチを利用し、片方のリストが空の場合はもう一 方のリストのみを返している。空ではない場合は小さいほうから順番に比較し ていき、同じ数の場合その個数が多いほうと同じになるようになっている。例 えば素因数に2が一つずつ含まれるリストをmergeした場合結果のリストには2が 一つ含まれるが、2が一つ含まれるリストと2が二つ含まれるリストをmergeした 場合結果のリストには2が二つ含まれる。これで二つの素因数のリストから必要 最低限の素因数のリストが求まる。

foldlはリストの要素に左から順番に関数を適用していく関数である。ここでは 初期値として空リスト使い、素因数のリストに順番にmerge関数を適用し、最終 的にすべての素因数のリストをmergeしたものが得られる。

euler005 = product $ foldl merge [] $ map (flip primeFactorize primes) [1..20]
    where merge x []      = x
          merge [] y      = y
          merge (x:xs) (y:ys)
              | x == y    = x : merge xs ys
              | x < y     = x : merge xs (y:ys)
              | otherwise = y : merge (x:xs) ys

上記のプログラムで答えを求めることはできるが、問題をもう一度見直してみ ると、問題文は回りくどい書き方をしているが、実際には1から20の最小公倍数 を求める問題であることがわかる。幸運にもHaskellには最小公倍数を求める 関数lcmがあるので、それを利用して次のように非常にシンプルにプログラムが かける。

euler005 = foldl lcm 1 [1..20]

回文になっている数はどちらから読んでも同一である。二つの2桁の数の積で作 られる回文で最大の数は9009=91×99である。

二つの3桁の数の積で作られる回文で最大のものを求めよ

例によってリストの内包表記で二つの3桁の数の積のうち回文になっているもの のリストを作ることにする。最大のものを求めるという問題の目的からして 100のような小さな数とか含める必要がないようにも思うがここは愚直に全てを 対象とした。maximum はリストの中から最大の要素を求める関数である。

問題となるのは回文かどうかを判定するところである。二つの3桁の数の積で最 大のものを求めるので対象の数は6桁と仮定。10万の位と1の位、1万の位と10の 位、1000の位と100の位が同じかどうかを比較することで回文の判定ができる。 美しさや汎用性はないがこれで答えは求まる。

isPalindrome6 n = (n `div` 100000) == (n `mod` 10)
                  && ((n `mod` 100000) `div` 10000) == ((n `mod` 100) `div` 10)
                  && ((n `mod` 10000) `div` 1000) == ((n `mod` 1000) `div` 100)

euler004 = maximum $ [x * y | x <- [100..999], y <- [100..999],
                      isPalindrome6 (x * y)]

13195の素因数は5,7,13,29である。

600851475143の一番大きな素因数を求めよ

せっかくHaskellを使っているので、まずは問題をシンプルかつ直感的にソース コードにしたようなナイーブなやり方を考える方針とする。もしそれが実行速度が遅すぎて答えが求まらないような場合は実行効率も考えたプログラムを考えることにする。

最近の高級言語はレジスタに入らないような大きな数も自動的にうまく扱ってくれるので問題の数字が大きいことは問題ない。これはこういう演習的な問題を解く上での労力の削減に大きく影響すると思う。HaskellだとInteger型で大きさを制限されない整数を扱うことが出来る。ただし、Haskellには強力な型推論があり、実際には型を明示しなくても勝手にうまく扱ってくれる。

素因数とは素数である約数なので、乱暴にいえば素数で順番に割っていき、割り切れた一番大きな素数を求めれば答えということになる。ここで素数をエラトステネスの篩を使って求めることにするが、これがまたHaskell的には得意分 野であると思う。よくある定義は以下のとおり。

sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]
primes = sieve $ 2 : [3, 5 ..]

そして問題を上記の乱暴なやり方でプログラムを書くと次のようになる。まず 目的の数より小さい素数のリストをtakeWhileでとりだす。次に、その中から目 的の数の約数をfilterで取り出す。ここで\x -> n `mod` x == 0というのは filterの条件をλ表記の無名の関数で定義している。引数がxで目的の数nをxで 割ったあまりが0 かどうか比較する関数という意味だ。これで目的の数を割り 切ることができる素数を取り出すことが出来る。最後にlastでリストの一番最 後の要素を取り出すことで一番大きな値を求めることが出来る。

この無名関数を用いたところを、Haskellの場合0と比較する関数とあまりを求 める関数を合成するという方法で書くこともできる。個人的にはそういう表記 にはなれていないこともあって、ここでは無名関数で書いた。ちなみに関数合 成を利用してよけいな変数を明示しないスタイルをポイントフリースタイルと いうそうだ。関数合成の演算子は.で、ここでは(== 0) . mod nと書くことで目 的の数nを引数で割ったあまりが0かどうかを比較する関数を表現できる。

euler003 = last $ filter (\x -> n `mod` x == 0) $ takeWhile (<= n) primes
    where n = 600851475143

一見これで問題解決のようだが、実際には上のプログラムは遅すぎて使い物に ならない。もし凄く速い実行環境を持っている場合は上のプログラムでもいい のだが、ここではもう少し高速なバージョンを考えることにする。

上記のプログラムで実行に時間がかかっているのは素数を求める部分である。 エラトステネスの篩で求める場合、求まった全ての素数について、それ以降の 数が倍数かどうかを試すことになるので、目的の数についてn^2程度のオーダー の時間がかかると考えられる。上記のやりかたでは600851475143という非常に 大きな数までの素数を求めなくてはいけないので計算が終了しない。

実はというか当然ではあるが素因数を求めるのに全ての素数で割ってみるとい うやり方はソースコードは単純になるが好ましいものではない。もっと普通の 求め方は、例えば13195の素因数を求める場合、まず5で割れるとわかるので5で 割ると2639になる。次に2639が7で割れるので7で割ると377になる。377が13で 割れるので13で割ると29になる。最大の素因数は29 とわかる。このとき13195 の最大の素因数を求めるのに29までの素数しか必要としない。

上で説明した素因数分解のやり方をそのままプログラムにしたのが関数 primeFactorizeである。引数に素因数分解したい数と素数のリストを渡すと素 因数のリストを返す。ここで素数のリストは無限リストであるがHaskellでは必 要なときに必要な分しか計算されない。

この関数では小さい素数から順に割れるかどうか試していくので、対象になる 数の平方根以上で割りきれることはない。Haskellでは|の後ろに条件を書くこ とで、条件ごとに関数の処理を分けることが出来るが、1行目そのチェックであ り、このときnは素因数なので返り値のリストに追加する。Haskellでは変数の 型を変更することが出来ないので、Floating型の値を扱う関数sqrtと整数とを 同時に扱うにはfromInteger関数で明示的に変換する必要がある。

2行目は素数で割り切れたときで、対象となる数を素数で割った値で次のチェッ クを行う。その素数は素因数なのでリストに追加する。同じ素数で複数回割り 切れることもあるので素数のリストは変更しない。3行目は割り切れなかったと きで、その素数では割り切れないので取り除いて次の素数でチェックする。

Haskellでは:を用いてp:psのようにリストを表記でき、pが最初の要素、psが2 番目以降の要素のリストとなる。関数の引数に(p:ps)とい書いた場合はパター ンマッチとなり引数に渡された値が、pにリストの先頭の要素、psにリストの残 りの要素という風にバインドされる。パターンにマッチしない引数（この場合 では空リスト）の場合はこの関数定義は使用されない。ここでは素数のリスト は無限リストであるが、呼び出しにマッチするパターンがなかった場合はエラー となる。

最後にprimeFactorize関数を使って600851475143 の素因数のリストを求め、そ の一番最後の値（最大の値）が問題の答えとなる。

primeFactorize n (p:ps)
    | fromInteger (p)
      > sqrt (fromInteger n) = [n]
    | n `mod` p == 0         = p : primeFactorize (n `div` p) (p:ps)
    | otherwise              = primeFactorize n ps

euler003 = last $ primeFactorize 600851475143 primes