有助于了解Etasthenes实施的筛选

这很无聊,我知道,但我需要一点帮助来理解埃拉托斯特尼筛的实现。这是解决 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) . 但我不明白 磷 和 斯塔克 ,这就是 (+ (* 2 i i) (* 6 i) 3) .

编辑 :我知道这个想法是跳过以前筛选过的数字。字谜定义指出,当筛选一个数字时 x ,筛选应从 X . 所以,当筛选3时,从消除9等开始。

然而,我不明白的是,作者是如何想出这个表达的 斯塔克 (代数地说)。

从拼图评论:

一般来说,当用n进行筛选时,筛选从n平方开始,因为之前所有n的倍数都已经过筛选。

表达式的其余部分与数字和筛选索引之间的交叉引用有关。表达式中有一个2,因为我们在开始之前消除了所有偶数。表达式中有一个3,因为方案向量是基于零的,数字0、1和2不是筛选的一部分。我认为6实际上是2和3的组合,但自从我研究代码以来,它已经有一段时间了,所以我会让你来搞清楚。

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