algorithm - 帮助了解Eratosthenes实现的筛网

我知道这很无聊，但是我需要一点帮助来理解Eratosthenes筛网的实现。这是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的表达式的(代数形式)。

从拼图评论:



如果有人可以帮助我，那就太好了。谢谢!

最佳答案

我想我已经在programmingpraxis的comments on their website的帮助下解决了。

为了重述该问题， list 中将startj定义为(+ (* 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)可能更清楚了，但是无论如何-我认为可以解决这个问题:)