從素篩功能返回矢量（定長陣列），並將其轉換爲以後的列表

Question

我發現了一個prime-sieve函數，它使用Eratosthenes篩計算第一個質數。該方法是根據高德納的算法，我從here複製它：

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

我得到的錯誤：

vector-ref: contract violation
expected: vector?
given: #t
argument position: 1st
other arguments...:

如果我在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))))) 

這會返回一個列表，而不是載體。這是因爲結果是逐步構建的，哪些列表適合，向量不適合。

我通過將結果與my implementation of the Sieve of Eratosthenes進行比較，驗證了上述代碼。

---

你使用Racket嗎？我注意到你在代碼中使用了add1。如果是這樣，這是同樣的算法，但在球拍使用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每次計算的，而不是積累，但我認爲這不是一個大問題。