代码之家 › 专栏 › 技术社区 › harto

有助于了解Etasthenes实施的筛选

sieve-of-eratosthenes puzzle scheme algorithm

5

harto · 技术社区 · 15 年前

这很无聊,我知道,但我需要一点帮助来理解埃拉托斯特尼筛的实现。这是解决 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的组合,但自从我研究代码以来,它已经有一段时间了,所以我会让你来搞清楚。

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

2 回复 | 直到 15 年前

1

4

harto 15 年前

我想我已经知道了,在编程实践的帮助下。 comments on their website .

为了重申这个问题, startj 在列表中定义为 (+ (* 2 i i) (* 6 i) 3) ,即 2i^2 + 6i + 3 .

我最初不明白这个表达与 p -从“筛选”数字开始 磷 应该开始 p^2 ,我想 斯塔克 应该是与 4i^2 + 12i + 9 .

然而, 斯塔克 是向量的索引 v ,包含从3开始的奇数。因此,指数 第2页 实际上是 (p^2 - 3) / 2 .

展开方程: (p^ 2—3)/2 = ([4i^2 + 12i + 9] - 3) / 2 = 2I^ 2 +6I+ 3 -它的价值是 斯塔克 .

我觉得应该更清楚地定义 斯塔克 作为 (quotient (- (* p p) 3) 2) 但不管怎样-我认为解决了它:)

2

3

programmingpraxis 15 年前

大卫·塞勒:也许不是最清楚的,但是除了实现基本筛选之外,它还必须实现练习中描述的三个优化。

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

短暂:正确。

在我的评论中看到更完整的解释 Programming Praxis .

编辑 :我在编程实践中添加了其他注释。当我真正看代码的时候,关于公式中6的推导,我错了;对不起,我误导了你。