main = do s <- getContents let n = read s ps = eulerPrimesTo (n+1) print (length ps, last ps) fromSpan (xs,i) = xs ++ fromSpan (map (+ i) xs,i) eulerS () = iterate eulerStep ([2],1) eulerStep (xs@(p:_), i) = ( (tail . concat . take p . iterate (map (+ i))) xs `minus` map (p*) xs, p*i ) eulerPrimesTo :: Int -> [Int] eulerPrimesTo m = if m > 1 then go ([2],1) else [] where go w@((p:_), _) | m < p*p = takeWhile (<= m) (fromSpan w) | True = p : go (eulerStep w) minus a@(x:xs) b@(y:ys) = case compare x y of LT -> x : minus xs b EQ -> minus xs ys GT -> minus a ys minus a b = a