基于Racket实现求≤n的质数的sieve函数问题求助

首先明确核心逻辑：埃氏筛不需要提前从n生成固定的除数列表，除数是在筛选过程中动态得到的——每次从候选列表里取出的第一个数必然是质数，用它过滤剩余元素后，递归处理新的候选列表即可。

结合你已经实现的drop-divisible和sieve-with，假设你的函数功能如下（如果和你的实际实现有出入，只需微调逻辑）：

• drop-divisible d lst：返回lst中所有不能被d整除的元素
• sieve-with candidates：接收候选数列表，返回其中的所有质数

最终sieve函数实现 #

(define (sieve n)
  (sieve-with (range 2 (+ n 1))))

补充sieve-with的正确实现（如果你的版本有问题） #

如果你的sieve-with还没完全符合逻辑，这里给出适配的递归实现：

(define (sieve-with candidates)
  (if (empty? candidates)
      '()
      (let ([next-prime (first candidates)])
        (cons next-prime
              (sieve-with (drop-divisible next-prime (rest candidates)))))))

执行流程说明（以sieve 10为例） #

1. 初始候选列表由(range 2 11)生成：'(2 3 4 5 6 7 8 9 10)
2. 取出第一个质数2，用drop-divisible 2过滤剩余元素，得到'(3 5 7 9)，递归处理这个新列表
3. 取出第一个质数3，过滤剩余元素得到'(5 7)，继续递归
4. 取出第一个质数5，过滤剩余元素得到'(7)，继续递归
5. 取出第一个质数7，过滤剩余元素得到空列表，递归返回空
6. 逐层拼接结果：(cons 7 '()) → '(7) → (cons 5 '(7)) → '(5 7) → (cons 3 '(5 7)) → '(3 5 7) → (cons 2 '(3 5 7)) → '(2 3 5 7)，完全符合测试用例要求。

关键思路 #

不需要提前构造除数列表，因为埃氏筛的核心就是用已找到的质数去过滤后续候选数，质数本身就是动态生成的除数，这也是筛法高效的原因。

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