# Project Euler 解答

## Project Euler Problem 010

Project Euler Problem 010

```import Control.Monad
import Data.Array.ST
import Data.Array.Unboxed
import Data.List

--無限リストを使ったエラトステネスの篩a
primes :: [Int]
primes = 2: f [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

n :: Int
n=2000000 :: Int
ans1 :: Int
ans1 = sum \$ takeWhile ( UArray Int Bool
era n = runSTUArray(
do{ a <- newArray (1,n) True :: ST s (STUArray s Int Bool);
writeArray a 1 False;
sequence_[do{ prime <- readArray a i;
when prime (sequence_[do{writeArray a k False} | k<-[i+i,i*3..n]]);
} |i<-[1..n]];
return a;
})

-- 003より。O(n^1.2)の篩
primes2 :: [Integer] --このアノテーションはずすとバグるので注意する
primes2 = 2 : ([3,5..] `minus` join [[p*p, p*p+2*p..] | p <- primes'])
where
primes' = 3 : ([5,7..] `minus` join [[p*p, p*p+2*p..] | p <- primes'])
join  ((x:xs):t)    = x : union xs (join (pairs t))
pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t
union (x:xs) (y:ys) = case (compare x y) of
LT -> x : union  xs  (y:ys)
EQ -> x : union  xs     ys
GT -> y : union (x:xs)  ys
union  xs     []    = xs
union  []     ys    = ys
minus (x:xs) (y:ys) = case (compare x y) of
LT -> x : minus  xs  (y:ys)
EQ ->     minus  xs     ys
GT ->     minus (x:xs)  ys
minus  xs     _     = xs
```
• はじめに
• プロジェクトオイラー問題
• リンク等