从素筛函数返回向量(固定长度数组)，并将其转换为列表。

Question

我找到了一个prime-sieve函数，它使用Eratosthenes的筛子来计算第一个n素数。该方法基于Donald的算法，我从这里中复制了它

; http://community.schemewiki.org/?sieve-of-eratosthenes
(define (prime-sieve n) 
  (let ((pvector (make-vector (+ 1 n) #t))) ; if slot k then 2k+1 is a prime 
    (let loop ((p 3) ; Maintains invariant p = 2j + 1 
               (q 4) ; Maintains invariant q = 2j + 2jj 
               (j 1) 
               (k '()) 
               (vec pvector)) 
      (letrec ((lp (lambda (p q j k vec) 
                     (loop (+ 2 p) 
                           (+ q (- (* 2 (+ 2 p)) 2)) 
                           (+ 1 j) 
                           k 
                           vec))) 
               (eradicate (lambda (q p vec) 
                            (if (<= q n) 
                                (begin (vector-set! vec q #f) 
                                       (eradicate (+ q p) p vec)) 
                                vec)))) 
        (if (<= j n) 
            (if (eq? #t (vector-ref vec j)) 
                (begin (lp p q j q (eradicate q p vec))) 
                (lp p q j k vec)) 
            #t))))) 

我想使用这个函数返回一个向量，该向量可以转换为一个带有sieve-to-list函数的列表。

(define (sieve-to-list s upperlimit)
  (let aux ((i 2) (acc '()))
    (if (> i upperlimit)
        (reverse acc)
        (if (= (vector-ref s i) 1)
            (aux (add1 i) (cons i acc))
            (aux (add1 i) acc)))))

不幸的是，我不确定第一个函数是否返回向量，因为(vector? (prime-sieve 1000))返回#f。当我运行下面的代码并尝试查看前1000个素数的列表时：

(sieve-to-list (prime-sieve 1000) 1000)

我知道错误：

向量-参考:违反合同 预期:矢量？ 给予：#t 论点立场:第一 其他论点.

如果我将prime-sieve中的#t更改为在“给定”之后显示的其他内容。

我对向量不太了解。如果筛子不返回向量，为什么它不返回，我如何使它返回向量？如果它确实返回一个向量，为什么我的转换函数不能工作？

Answer 1

链接到的代码打印素数，但不存储它们或以任何方式返回它们。要存储它们，您应该像在sieve-to-list中一样使用累加器技术。无论如何，这里有一个固定版本(我也利用这个机会清理了大量代码)：

(define (prime-sieve n)
  (define vec (make-vector (+ n 1) #t))
  (let loop ((p 3) ; Maintains invariant p = 2j + 1
             (q 4) ; Maintains invariant q = 2j + 2jj
             (j 1)
             (result '(2)))
    (define (lp result)
      (loop (+ p 2)
            (+ q p p 2)
            (+ j 1)
            result))
    (define (eradicate!)
      (do ((q q (+ q p)))
          ((> q n))
        (vector-set! vec q #f)))

    (cond ((> j n) (reverse result))
          ((vector-ref vec j) (eradicate!)
                              (lp (cons p result)))
          (else (lp result)))))

这将返回一个列表，而不是一个向量。这是因为结果是逐步建立的，列表是好的，而向量不是。

通过将结果与Eratosthenes筛的实现进行比较，我验证了上述代码。

你用球拍吗？我注意到您在代码中使用了add1。如果是这样的话，下面是相同的算法，但是在Racket中使用for理解，它更简洁，更容易读懂：

(define (prime-sieve n)
  (define vec (make-vector (add1 n) #t))
  (define (eradicate! p q)
    (do ((q q (+ q p)))
        ((> q n))
      (vector-set! vec q #f)))
  (cons 2 (for/list ((j (in-range 1 (add1 n)))
                     #:when (vector-ref vec j))
            (define p (+ j j 1))
            (eradicate! p (* 2 j (add1 j)))
            p)))

在这个版本中，p和q每次都是从j中重新计算出来的，而不是累积起来的，但我不认为这是个大问题。