Algorithm

用厄拉多塞法筛选素数

最近在看SICP，这本书写的确实不错。3.5节中讲到了无穷流对素数的一个应用：用厄拉多塞筛法来构造出素数的无穷流。这个筛选思路值得记录一下。

厄拉多塞是公元前3世纪希腊亚历山大的哲学家。他由于第一个给出了地球的圆周的精确估计而闻名。他的计算方式是观察夏至日正午影子的角度。虽然厄拉多塞筛法历史如此悠久，但仍成为专用硬件“筛”的基础，直至最近都一直是确定大素数存在的有力工具。直到20世纪70年代，这种算法被概率算法超越。

思路

（前面关于流和无穷流的定义以及说明直接略过了，感兴趣的可以自己看）首先，这个无穷流从整数2开始，因为这是第一个素数。为了得到其余的素数，就需要从2后面的整数中过滤掉所有2的倍数，这样就留下一个从3开始的无穷流，而3也就是下一个素数。现在再从这个流的后面部分过滤掉所有3的倍数，这样就留下一个从5开头的无穷流，而5又是下一个素数，就这样继续下去。换句话说，这种方法就是通过一个筛选过程构造出各个素数。

筛选过程描述如下

对流S做筛选就是形成一个流，其中的第一个元素就是S的第一个元素，得到其随后的元素的方式是从S的其余元素中过滤掉所有S的第一个元素的倍数，而后再对得到的结果进行同样的筛选。

代码

1
2
3
4
5
6
7
8
9
(define (sieve stream)
  (cons-stream
    (stream-car stream)
    (sieve (stream-filter
                 (lambda  (x)
                      (not (divisible? x (stream-car stream))))
                (stream-car stream)))))

(define primes (sieve (integers-starting-from 2)))

上面的Lisp代码写得还是很精练的，没有任何多余的代码。

1574

我们可以将上面的厄拉多塞筛法看作是一个信号处理系统。出入流溃入“反cons”，分解出这个流的首元素和其余元素，用这个首元素去构造一个可除性过滤取，让该流的其余部分穿过这个过滤器，这个过滤器的输出再溃入到另一个筛块，而后将原来的首元素cons到这个内部筛的输出上，形成最终的输出流。这样，不仅输入流是无穷的，信息处理器也是无穷的。