我们可以改进 SICP 的素数筛代码吗

最近问答入口 https://stackoverflow.com/questions/73689215/need-help-to-understand-some-of-the-sicp-streams-examples展示了使用惰性流从 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)))

一个答案 https://stackoverflow.com/a/73695449/849891有显示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)用这个代码。

我们可以做得更好吗？

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

为此，我们将使用素数及其平方。我们将使用same生成这些素数的代码，我们需要生成这些素数our primes:

(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)))))

Now this导致

  (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. True sieve埃拉托斯特尼的应该运行在n log n log log n根据经验，这通常接近于n^1.1..1.2或左右。但是这个n^1.5也比原来的二次算法有了很大的改进，并且在实践中绝对运行速度也比它快得多。

顺便说一句，改变(not (divisible? x n)) to ((not-divisible-by n) x) https://stackoverflow.com/questions/66348123/sieve-of-eratosthenes-in-scheme-using-mutation-of-local-state-in-its-filtering-p/849891将我们的代码打开到全新的一行算法的改进，仅使用添加（并且没有尝试划分），就像原始版本一样，从大约 2000 年前开始。