我们能否改进 SICP 的这个素数筛代码

Question

最近的一个问答条目展示了以下使用惰性流从 SICP 生成代码的素数：

(define (sieve stream)
(cons-stream
(stream-car stream)
(sieve (stream-filter
(lambda (x)
(not (divisible? x (stream-car stream))))
(stream-cdr stream)))))
(define primes (sieve (integers-starting-from 2)))

那里的答案显示，除其他可能性外，primes等同于以下几种：

(cons-stream 2
(cons-stream 3
(cons-stream 5
(cons-stream 7
(sieve 
(stream-filter (lambda (x) (not (divisible? x 7)))
(stream-filter (lambda (x) (not (divisible? x 5)))
(stream-filter (lambda (x) (not (divisible? x 3)))
(stream-filter (lambda (x) (not (divisible? x 2)))
(integers-starting-from 9))))))))))

这里似乎有太多的过滤流——例如 7 是通过按 2、3 和 5 过滤输入数字产生的，而实际上只需要单独用 2 进行测试——只有 9 以上的数字真正需要测试除以 3，更不用说除以 5 等。

随着我们继续产生这种素数流，这个问题变得越来越明显。总的来说，生成前n素数需要使用此代码O(n^2)。

我们能做得更好吗？

Answer 1

事实上，我们只需要在输入中遇到素数的平方后才开始过滤掉素数的倍数。

为此，我们将使用素数及其平方。我们将使用相同的代码来生成这些素数，这是我们生成素数所必需的：

(define (pprimes) 
(cons-stream 2
(psieve (stream-map (lambda (x) (cons x (* x x)))
(pprimes))     ;; here 
(integers-starting-from 3))))
(define (psieve pr-sqrs numbers)       ;; prime+square pairs
(if (< (stream-car numbers)          
(cdr (stream-car pr-sqrs)))   ;; prime's square
(cons-stream 
(stream-car numbers)
(psieve pr-sqrs                 ;; same prime+square pair
(stream-cdr numbers)))  ;;   for the next number
(psieve 
(stream-cdr pr-sqrs)            ;; advance prime+square's stream
(stream-filter                  ;; and start filtering 
(let ((p  (car (stream-car pr-sqrs)))) ;; by this prime now
(lambda (x)
(not (divisible? x p))))
(stream-cdr numbers)))))

现在这导致

(pprimes)
=
....
=
(cons-stream 2
(cons-stream 3
(cons-stream 5
(cons-stream 7
(cons-stream 11
(cons-stream 13
(cons-stream 17
(cons-stream 19
(psieve (cons-stream 5 ... )
(cons-stream 25 ... )
(stream-filter (lambda (x) (not (divisible? x 3)))
(stream-filter (lambda (x) (not (divisible? x 2)))
(integers-starting-from 20))))))))))))
=
....

毫无疑问，这要好得多。低于 25 的数字不会被 5 等测试。

这仍然是审判部门，运行时间约为n^1.5.真正的埃拉托色尼筛子应该在经验上通常接近n^1.1..1.2或大约n log n log log n运行。但是这个n^1.5也是对原始二次算法的极大改进，并且在实践中在绝对值上也会比它运行得更快。

顺便说一下，将(not (divisible? x n))更改为((not-divisible-by n) x)为我们的代码打开了全新的算法改进线，仅使用添加(并且没有尝试除法)，就像~2000年前的原始版本一样。