Giúp hiểu Sàng thực hiện Eratosthenes

Question

Điều này thật nhàm chán, tôi biết, nhưng tôi cần một chút trợ giúp để hiểu được việc thực hiện Sàng Eratosthenes. Đó là giải pháp cho this Programming Praxis problem.

(define (primes n) 
    (let* ((max-index (quotient (- n 3) 2)) 
     (v (make-vector (+ 1 max-index) #t))) 
    (let loop ((i 0) (ps '(2))) 
     (let ((p (+ i i 3)) (startj (+ (* 2 i i) (* 6 i) 3))) 
     (cond ((>= (* p p) n) 
       (let loop ((j i) (ps ps)) 
        (cond ((> j max-index) (reverse ps)) 
         ((vector-ref v j) 
          (loop (+ j 1) (cons (+ j j 3) ps))) 
         (else (loop (+ j 1) ps))))) 
       ((vector-ref v i) 
       (let loop ((j startj)) 
        (if (<= j max-index) 
         (begin (vector-set! v j #f) 
          (loop (+ j p))))) 
         (loop (+ 1 i) (cons p ps))) 
       (else (loop (+ 1 i) ps))))))) 

Phần tôi đang gặp sự cố là startj. Bây giờ, tôi có thể thấy rằng p sẽ chuyển động qua các số lẻ bắt đầu từ 3, được định nghĩa là (+ i i 3). Nhưng tôi không hiểu mối quan hệ giữa p và startj, là (+ (* 2 i i) (* 6 i) 3).

---

Sửa: Tôi hiểu rằng ý tưởng là để bỏ qua số rây trước đó. Định nghĩa câu đố cho biết rằng khi chọn lọc số x, việc chọn lọc sẽ bắt đầu tại hình vuông x. Vì vậy, khi chọn 3, bắt đầu bằng cách loại bỏ 9, v.v.

Tuy nhiên, điều tôi không hiểu là cách tác giả đưa ra biểu thức đó cho startj (đại số nói).

Từ các ý kiến ​​câu đố:

Nói chung, khi chọn lọc bởi n, chọn lọc bắt đầu từ n-squared bởi vì tất cả các bội trước của n đã được sieved.

Phần còn lại của biểu thức phải làm với tham chiếu chéo giữa các số và chỉ mục sàng. Có 2 trong biểu thức vì chúng tôi đã loại bỏ tất cả các số chẵn trước khi chúng tôi bắt đầu. Có 3 trong biểu thức vì các vectơ Scheme không dựa trên 0 và các số 0, 1 và 2 không phải là một phần của rây. Tôi nghĩ rằng 6 thực sự là một sự kết hợp của 2 và 3, nhưng nó đã được một thời gian kể từ khi tôi nhìn vào mã, vì vậy tôi sẽ để nó cho bạn để tìm ra.

---

Nếu bất cứ ai có thể giúp tôi với điều này, rằng sẽ thật tuyệt. Cảm ơn!

Answer 1

Tôi nghĩ rằng tôi đã tìm ra nó, với sự hỗ trợ của lập trình viên 'comments on their website.

Để xác định lại vấn đề, startj được định nghĩa trong danh sách như (+ (* 2 i i) (* 6 i) 3), ví dụ: 2i^2 + 6i + 3.

Tôi không hiểu làm thế nào ban đầu biểu hiện này liên quan đến p - kể từ khi 'chọn lọc' đối với một số p nên bắt đầu từ p^2, I figured rằng startj nên một cái gì đó liên quan đến 4i^2 + 12i + 9.

Tuy nhiên, startj là chỉ mục trong vector v, có chứa số lẻ bắt đầu từ 3. Do đó, chỉ mục cho p^2 thực ra là (p^2 - 3)/2.

Mở rộng phương trình: (p^2 - 3)/2 = ([4i^2 + 12i + 9] - 3)/2 = 2i^2 + 6i + 3 - giá trị là startj.

tôi cảm thấy nó có thể đã rõ ràng hơn để xác định startj như (quotient (- (* p p) 3) 2), nhưng dù sao - Tôi nghĩ rằng giải quyết nó :)

Answer 2

David Seiler: có lẽ không rõ ràng nhất, nhưng ngoài việc triển khai Sàng cơ bản, nó cũng phải thực hiện ba tối ưu hóa được mô tả trong bài tập.

Harto: đó là bài tập thứ hai của tôi. Tôi vẫn đang thử nghiệm phong cách viết của mình.

Ephemient: correct.

Xem giải thích đầy đủ hơn trong nhận xét của tôi tại Programming Praxis.

EDIT: Tôi đã thêm nhận xét bổ sung tại Lập trình Praxis. Và khi tôi thực sự xem xét mã, tôi đã sai về đạo hàm của số 6 trong công thức; xin lỗi tôi đánh lừa bạn.