Haskell优化埃氏筛法问询：新手求高效素数列表生成方案

嘿，作为Haskell新手碰到素数生成的性能问题太正常啦！你的代码思路是对的，但确实因为每次处理素数时都要重新遍历整个列表生成新副本，导致效率被拖了后腿。其实Haskell完全能写出符合O(n log n log log n)复杂度的高效素数生成代码，而且还能保持函数式编程的简洁性～

先聊聊你代码里的核心问题：每次找到素数y时，你通过列表推导式遍历[0..x]的所有元素来生成新列表，这相当于每次都要扫描整个范围，而不是只标记y的倍数。这也是为什么你的代码比过程式实现慢很多的原因。

下面给你几个不同场景下的高效实现：

1. 简洁的无限素数列表（惰性求值版） #

如果你不需要预先设定上限，只想生成无限的素数序列，这个版本最优雅，而且效率很高：

primes :: [Integer]
primes = sieve [2..]
  where
    sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

这个实现利用了Haskell的惰性求值特性：每次取出列表的第一个元素p（它肯定是素数），然后筛掉后面所有能被p整除的数，剩下的列表继续递归筛。因为惰性，它不会一次性生成所有数，只会在你需要的时候计算下一个素数，时间复杂度就是标准的埃氏筛复杂度。

2. 带上限的素数标记数组（高效ST数组版） #

如果你需要像你原来代码那样，生成一个索引对应数字、值表示是否为素数的数组，推荐用STUArray来实现——它能在保证纯函数性的前提下，像过程式代码一样高效地原地更新数组：

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

primeArray :: Int -> UArray Int Bool
primeArray n = runSTUArray $ do
    -- 初始化数组：所有数默认标记为素数
    arr <- newArray (0, n) True
    -- 0和1不是素数
    writeArray arr 0 False
    writeArray arr 1 False
    let sieve p
          -- 优化：只需要筛到sqrt(n)，之后剩下的都是素数
          | p*p > n = return arr
          | otherwise = do
              isPrime <- readArray arr p
              if not isPrime
                  -- 当前p不是素数，直接跳过
                  then sieve (p+1)
                  else do
                      -- 标记p的所有倍数（从p²开始，因为更小的倍数已经被之前的素数标记过了）
                      mapM_ (\i -> writeArray arr i False) [p*p, p*p+p..n]
                      sieve (p+1)
    sieve 2

这个版本和过程式的埃氏筛效率几乎一致，因为它直接在数组上修改标记，不需要每次生成新列表，完美实现了O(n log n log log n)的复杂度。

3. 基于普通列表的优化版（如果不想用数组） #

如果你暂时不想引入数组库，也可以优化你原来的列表实现，只标记素数的倍数而不是遍历整个列表：

primeList :: Int -> [Bool]
primeList n = sieve 2 initialList
  where
    initialList = [False, False] ++ replicate (n-1) True
    sieve p lst
      | p*p > n = lst
      | not (lst !! p) = sieve (p+1) lst
      | otherwise = sieve (p+1) (markMultiples lst p)
    -- 只标记p的倍数（从p²开始）
    markMultiples lst p = foldr (\i acc -> take i acc ++ [False] ++ drop (i+1) acc) lst [p*p, p*p+p..n]

不过要注意，普通列表是链表结构，随机更新的效率不如数组，所以这个版本的性能会比数组版差一些，但已经比你原来的代码高效很多了。

最后纠正一个小误解：你觉得函数式编程特性无法实现高效版本，其实是不对的～Haskell的惰性求值和纯函数性反而能让埃氏筛的实现更优雅，关键是要选对数据结构（比如数组）或者利用惰性列表的特性，避免不必要的全列表遍历。

内容的提问来源于stack exchange，提问作者Alex Costea