5

这很无聊，我知道，但我需要一点帮助来理解 Eratosthenes 筛的实现。这是这个编程实践问题的解决方案。

(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)。但我不明白 and 之间的关系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的组合，但是我看代码已经有一段时间了，所以我把它留给你去弄清楚。

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

4

2 回答 2

4

我想我已经想通了，在他们网站上编程实践的评论的帮助下。

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

于 2009-10-21T05:12:14.093 回答
3

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

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

幻象：正确。

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

编辑：我在 Programming Praxis 添加了附加评论。而当我实际查看代码时，我对公式中数字 6 的推导是错误的；对不起，我误导了你。

于 2009-10-21T02:41:05.400 回答