algorithm - 帮助理解埃拉托色尼筛法的实现

Question

这很无聊，我知道，但我需要一些帮助来理解埃拉托色尼筛法的实现。这是 this Programming Praxis problem 的解决方案.

(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 开始的奇数，定义为 (+ i i 3)。但是我不明白p和startj之间的关系，就是(+ (* 2 i i) (* 6 i) 3) .

---

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

但是，我不明白作者是如何得出 startj 的表达式(从代数上讲)。

来自拼图评论:

In general, when sifting by n, sifting starts at n-squared because all the previous multiples of n have already been sieved.

The rest of the expression has to do with the cross-reference between numbers and sieve indexes. There’s a 2 in the expression because we eliminated all the even numbers before we ever started. There’s a 3 in the expression because Scheme vectors are zero-based, and the numbers 0, 1 and 2 aren’t part of the sieve. I think the 6 is actually a combination of the 2 and the 3, but it’s been a while since I looked at the code, so I’ll leave it to you to figure out.

---

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

Answer 1

在 programmingpraxis 的帮助下，我想我已经弄明白了 comments on their website .

重申一下问题，startj 在 list 中定义为 (+ (* 2 i i) (* 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 (- (* p p) 3) 2) 可能更清楚，但无论如何 - 我认为这解决了问题:)