帮助理解Sierat of Eratosthenes的实施

Question

我知道,这很无聊,但我需要一些帮助来理解Eratosthenes筛子的实施.这是编程Praxis问题的解决方案.

(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(代数说).

从拼图评论:

通常,当筛选n时,筛选开始于n平方,因为所有先前的n的倍数已经被筛分.

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

---

如果有人能帮助我,那就太好了.谢谢!

Answer 1

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

重述该问题，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)，但无论如何 - 我认为这解决了它:)