Return 来自素筛函数的向量（定长数组），稍后将其转换为列表

Question

我找到了一个 prime-sieve 函数，它使用埃拉托色尼筛法计算前 n 个素数。该方法基于 Donald Knuth 的算法，我从 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)))))

我想将该函数用于 return 一个可以使用函数 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)))))

不幸的是，我不确定第一个函数 return 是否是向量，因为 (vector? (prime-sieve 1000)) returns #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 更改为显示在 "given" 之后的其他内容。

我对向量了解不多。如果筛子不是 return 向量，为什么不是，我怎样才能使它 return 成为向量？如果它 return 是一个向量，为什么我的转换函数不起作用？

Answer 1

您链接到 的代码打印 素数，但不存储它们或 return 它们以任何方式。要存储它们，您应该像 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)))))

这return是一个列表，而不是向量。那是因为结果是逐步构建的，哪些列表适合哪些向量，哪些不适合。

我通过将结果与 my implementation of the Sieve of 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重新计算而不是累加，但我认为这不是一个大问题。

Return 来自素筛函数的向量（定长数组），稍后将其转换为列表

Return vector (fixed-length array) from prime-sieve function and convert it to list later

scheme