Haskell初学者实现埃氏筛法遇错误：or函数参数使用不当

编译错误原因 #

1. or与||混淆：Haskell里or是对布尔列表做折叠运算（比如or [True, False]），只能接受一个布尔容器参数；而你需要的是两个布尔值的逻辑或，应该用二元运算符||。
2. 类型不匹配：mod n x返回的是整数，无法直接参与逻辑运算，必须转换成布尔值，比如用mod n x == 0判断n是否能被x整除。

逻辑问题修正 #

你的divl函数参数顺序和终止逻辑不符合埃氏筛的需求：埃氏筛需要判断候选数x是否能被已找到的质数整除，而非判断质数列表里是否有能被x整除的数。同时空列表没有元素能整除x，终止条件应返回False而非True。

修正后的代码 #

erat primes [] = primes
erat primes (x:xs)
  | divl x primes = erat primes xs
  | otherwise = erat (primes ++ [x]) [y | y <- xs, y `mod` x /= 0]

divl _ [] = False
divl x (n:l) = (x `mod` n == 0) || divl x l

代码说明 #

• divl x l：判断x是否能被列表l中的任意元素整除，用于识别非质数。
• erat函数：
  • 候选列表为空时，返回已收集的质数列表；
  • 若候选数x是质数（不能被已有的质数整除），则将其加入质数列表，并过滤掉候选列表中所有能被x整除的数后继续递归；
  • 若x是非质数，则直接跳过，继续处理剩余候选数。

测试调用示例：erat [] [2..10]会返回[2,3,5,7]，符合埃氏筛的预期结果。

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