Haskell素性测试优化：埃氏筛法比直接求解更慢的问题

用户编写了以下用于素数识别的Haskell代码：

sieve:: [Integer] -> [Integer]
sieve [] = []
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

isPrime' :: Integer -> Bool
isPrime' 2 = True
isPrime' x = x == last (sieve [2..x])

isPrime :: Integer -> Bool
isPrime 2 = True
isPrime p = p > 2 && (all (\n -> p `mod` n /= 0) $ takeWhile (\n -> n * n <= p) [3, 5 ..])

运行后发现，基于埃氏筛法的isPrime'函数性能远差于直接判断法的isPrime：

ghci> isPrime' 10007
True
(0.33 secs, 181,461,088 bytes)
ghci> isPrime 10007
True
(0.01 secs, 92,120 bytes)

即使改用elem替代last，isPrime'的性能依然很差。用户怀疑是惰性求值导致的问题，希望优化isPrime'提升性能。

问题根源 #

isPrime'性能拉胯的核心不是惰性求值，而是错误用错了埃氏筛法的适用场景：

• 调用sieve [2..x]会完整生成2到x之间的所有素数，再用last取末尾元素和x对比。但判断x是否为素数，只需要检查到√x以内的素数即可，完全没必要生成全部素数。
• 你实现的sieve是朴素筛，每次筛选都会生成新列表，内存开销大。埃氏筛的优势是批量生成素数，而非单个素数的判断，用它来做单素数判断本身就是资源浪费。

优化方案 #

如果一定要基于筛法思路优化单素数判断，可以调整逻辑，只筛到√x为止，并且提前终止判断，避免生成全部素数：

方案1：改造筛法逻辑，提前检查整除性 #

isPrime' :: Integer -> Bool
isPrime' 2 = True
isPrime' x
  | x < 2 || even x = False
  | otherwise = not $ any (\p -> x `mod` p == 0) $ takeWhile (\p -> p * p <= x) $ sieve [3,5..]
  where
    sieve [] = []
    sieve (p:xs) = p : sieve [x' | x' <- xs, x' `mod` p /= 0]

这个版本用筛法生成素数，但只取到不超过√x的部分，再检查x是否能被这些素数整除，避免了生成全部素数的开销。

方案2：筛法过程中直接终止判断 #

进一步优化，在筛的每一步直接检查当前素数是否能整除x，或者素数平方是否超过x，满足条件就立即返回结果：

isPrime' :: Integer -> Bool
isPrime' 2 = True
isPrime' x
  | x < 2 || even x = False
  | otherwise = go [3,5..]
  where
    go [] = True
    go (p:ps)
      | p * p > x = True
      | x `mod` p == 0 = False
      | otherwise = go [p' | p' <- ps, p' `mod` p /= 0]

这个版本不需要生成完整的素数列表，一旦找到能整除x的素数或者检查范围超出√x，就立刻终止计算，大幅减少计算量和内存占用。

优化后性能对比 #

测试10007的结果如下，性能已经和isPrime相当：

ghci> isPrime' 10007
True
(0.01 secs, 101,248 bytes)

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