帮助理解埃拉托斯特尼筛法的实现

Question

我知道这很无聊，但我需要一些帮助来理解埃拉托斯特尼筛法的实现。这是这个编程实践问题的解决方案。

(define (primes n)
  (let* ((max-index (quotient (- n 3) 2))
         (v (make-vector (+ 1 max-index) #t)))
    (let loop ((i 0) (ps '(2)))
      (let ((p (+ i i 3)) (startj (+ (* 2 i i) (* 6 i) 3)))
        (cond ((>= (* p p) n)
               (let loop ((j i) (ps ps))
                  (cond ((> j max-index) (reverse ps))
                        ((vector-ref v j)
                          (loop (+ j 1) (cons (+ j j 3) ps)))
                        (else (loop (+ j 1) ps)))))
              ((vector-ref v i)
                (let loop ((j startj))
                  (if (<= j max-index)
                      (begin (vector-set! v j #f)
                             (loop (+ j p)))))
                      (loop (+ 1 i) (cons p ps)))
              (else (loop (+ 1 i) ps)))))))

我遇到问题的部分是 startj。现在，我可以看到 p 将从 3 开始循环奇数，定义为 (+ ii 3)。但我不明白p和startj之间的关系，即(+ (* 2 ii) (* 6 i) 3) 。

---

编辑：我知道这个想法是跳过以前筛选的数字。谜题定义指出，当筛选数字 x 时，筛选应从 x 的平方开始。因此，当筛选 3 时，首先消除 9 等。

但是，我不明白的是作者如何想出 startj 的表达式（从代数角度来说）。

来自拼图评论：

一般来说，当按n筛选时，筛选从n次方开始，因为之前所有n的倍数都已被筛选。

表达式的其余部分与数字和筛索引之间的交叉引用有关。表达式中有一个 2，因为我们在开始之前就消除了所有偶数。表达式中有 3，因为Scheme 向量是从零开始的，并且数字 0、1 和 2 不是筛子的一部分。我认为 6 实际上是 2 和 3 的组合，但是我已经有一段时间没有查看代码了，所以我将它留给你来弄清楚。

---

如果有人能帮助我解决这个问题，那就太好了。谢谢！

Answer 1

我想我已经在programmingpraxis的评论的帮助下找到了答案他们的网站。

为了重述该问题，startj 在清单中定义为 (+ (* 2 ii) (* 6 i) 3)，即 2i^2 + 6i + 3。

我最初并不理解这个表达式如何与 p 相关 - 因为数字 p 的“筛选”应该从 p^2 开始，我我认为 startj 应该与 4i^2 + 12i + 9 相关。

但是，startj 是向量 v 的索引，其中包含从 3 开始的奇数。因此，p^2 的索引实际上是(p^2 - 3) / 2。

展开方程：(p^2 - 3) / 2 = ([4i^2 + 12i + 9] - 3) / 2 = 2i^2 + 6i + 3 - 这是startj 的值。

我觉得将 startj 定义为 (quotient (- (* pp) 3) 2) 可能会更清楚，但无论如何 - 我认为这解决了它:)

Answer 2

David Seiler：也许不是最清楚，但除了实现基本的 Sieve 之外，它还必须实现练习中描述的三个优化。

哈托：这是我的第二个练习。我仍在尝试我的写作风格。

埃菲米特：正确。

请参阅我的评论中的更完整的解释 Programming Praxis 。

编辑：我在编程实践中添加了一条附加评论。而当我真正看代码时，我对公式中数字6的推导是错误的；抱歉我误导了你。