project euler problem 10

problem 10をときなおしてみた。

import Data.Time

main=do
  stime <- getCurrentTime
  print $  sum $ takeWhile (<2000000) primes
  getCurrentTime >>= return.(`diffUTCTime` stime) >>= print

primes = 2:[x|x<-[3,5..],isPrime x]

isPrime x = all ((/=0).(mod x)) $ takeWhile (\y->y^2<=x) primes

実行結果

*Main> 142913828922
33.037461s

ghciで30秒台なのでいいんじゃないかな。

今後の課題は (\y->y^2<=x)をラムダ式なしで表現すること

isPrime x = all ((/=0).(mod x)) $ takeWhile (<(floor(sqrt x))) primes

これだと型の問題をおこしてるんだよな。
型宣言を行いつつ　sqrtにfromIntegralでIntegerを型の特定されていない数に戻して
（Intの表現を越えているのでIntegerにした）

primes::[Integer]
primes = 2:[x|x<-[3,5..],isPrime x]

isPrime::Integer->Bool
isPrime x = all ((/=0).(mod x)) $ takeWhile (<= (floor.sqrt.fromIntegral) x) primes

実行時間が激変した

*Main>
142913828922
16.961851s

やっぱhaskellで型は大事だなぁ。

あ、よく考えたら合成関数でやればよかった

isPrime'::Integer->Bool
isPrime' x = all ((/=0).(mod x)) $ takeWhile ((<=x).(^2)) primes

まあ、型の勉強ができたので吉とするか。