project euler problem 1-3

久しぶりに暇してるのでeulerをやってみることにした。

問題は以下
http://projecteuler.net/index.php?section=problems

日本語訳も見つけたのでここからコピペしながら進行
http://odz.sakura.ne.jp/projecteuler/index.php?Project%20Euler

問題１

10未満の自然数のうち、3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり、 これらの合計は 23 になる。

同じようにして、1,000 未満の 3 か 5 の倍数になっている数字の合計を求めよ。

Prelude> sum [x|x<-[1..999],mod x 3==0||mod x 5==0]
233168

問題２

フィボナッチ数列の項は前の2つの項の和である。 最初の2項を 1, 2 とすれば、最初の10項は以下の通りである。

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。

--problem 2
main=putStrLn $ show problem
problem = sum $ filter even $ takeWhile (<4000000) fib
fib = 1:2:zipWith (+) fib (tail fib)

答えをコピペし間違えてしばらく悩んでしまった。

問題３

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

600851475143 の素因数のうち最大のものを求めよ。

そ、素数ですか…中学生以来組んだことのない素数ですか。一時間悩んだ後　素数のリストを返す関数は以下

main=putStrLn $ show problem
problem = primeList 10
primeList x | x==1 = []
            | x==2 = [2]
            | otherwise = primeList (x-1) ++ if or $ map (\a->mod x a==0) (primeList (x-1)) then []\
 else [x]

100とか入れるとすでに計算できない。そりゃそうか計算結果を保存してないものな…
というか or $ map (\a->mod x a==0) (primeList (x-1)) この辺ですでに頭崩壊

こりゃ、リストから削っていく方法をとるしかないな。ってそれが本来の エラトステネスの篩か…

main=putStrLn $ show problem
problem = primeList 100
primeList x = plist [2..x]
plist (x:xs) = if xs==[] then [x] else x:plist (filter (\a->mod a x/=0) xs)

よし、任意の数字以内の素数のリストは作ることに成功した。

あれ？もしかしてこのまま行くと最大の素数でmodでフィルタかけて　lastってか？できないことはないけどかっこわるくね？まあやるか　

main=putStrLn $ show problem
--problem = factor 13195
problem = factor 600851475143
--factor x = last $ filter (\a->mod x a==0) $ plist [2..(div x 2)]
factor x = filter (\a->mod x a==0) $ plist [2..(div x 2)]
plist (x:xs) = if xs==[] then [x] else x:plist (filter (\a->mod a x/=0) xs)

これ、エラトステネスの篩　のやりかたじゃないよな。haskellくさくない。
というかlastのバージョンだと終わらない　600851475143 div 2 まで計算するからだよな。
もう少し高速化したいなぁ

一般に素因数分解は、対象の数 n について、その平方根以下の全ての素数について n を割ってみる。しかし、これは n が大きい場合に対象となる全ての素数が明らかでないという問題が生じる。

だよなぁ。他の方法は…他の人に教えてもらった方法

--problem 3

main=putStrLn $ show problem

problem = factor 600851475143 2
factor x y = if (mod x y)==0&&x/=y then
                 factor (div x y) y
             else if x <= y then x else factor x (y+1)

エラトステネスのふるいによると小さい方から割っていくといいはずなので…まあ、y+1ってことで素数でないものでも割っているからその分のタイムロスはあると思うがほぼ一瞬で終わる。
よく考えると判明した素数のリストを再帰先にもちわわった場合の検索コストと対して変わらないので諦めた

$ time ./a.out 
6857
real:0m0.003s,user:0m0.000s,sys:0m0.000s

なんかunfoldrでできそうな気がするんだがだめだw