Project Euler 解答

Project Euler Problem 058

Project Euler Problem 058

```import Data.Array

primes :: [Integer]
primes = 2:f [3] [3,5..] where
f (x:xs) ys = ps ++ f (xs++ps) [z | z<-qs,z`rem`x/=0] where
(ps,qs) = span (< x*x) ys
isPrime :: Integer -> Bool
isPrime nn = imp nn primes where
imp n (p:ps) = if n< p*p then True
else if n`rem`p==0 then False
else imp n ps
zobun :: [Integer]
zobun = concatMap(\x->x:[x]) [1..]
alist :: [Integer]
alist = scanl1 (+) (1:zobun)
--サイドレングスnの時のリスト
nlist :: Int -> [Integer]
nlist n = tail \$ zipWith (+) (cycle [0,-1,0,0]) \$ take (2*n) alist
limit :: Int
limit = 100000
--配列を使ってメモ化
nlista :: Array Int Integer
nlista = listArray (1,limit) \$ nlist limit
sums_ :: Array Int Int
sums_ = a where
a = listArray (1,limit) (0:[imp i | i<-[2..limit]])
imp n = let aug = length \$ filter isPrime \$ map (nlista!) [2*(n-1),2*(n-1)+1] in
a!(n-1)+aug
ratios :: [Double]
ratios = zipWith (\x y -> fromIntegral x / fromIntegral (2*y-1)) (tail \$ elems sums_) ([2..]::[Integer])
ans1 :: Integer
ans1 = snd \$ head \$ filter ((<0.100000001).fst) \$ zip ratios [2..]
--26241
main :: IO ()
main = print ans1
```
• はじめに
• プロジェクトオイラー問題
• リンク等