Pomóż zrozumieć implementację Sieve of Eratostenes

Question

To jest nudne, wiem, ale potrzebuję trochę pomocy w zrozumieniu implementacji Sieve of Eratostenes. Jest to rozwiązanie dla 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))))))) 

Część, z którą mam problem, to startj. Teraz widzę, że p będzie przechodzić przez nieparzyste liczby zaczynające się od 3, zdefiniowane jako (+ i i 3). Ale nie rozumiem związku między p i startj, który jest (+ (* 2 i i) (* 6 i) 3).

---

Edit: Rozumiem, że chodzi o to, aby pominąć uprzednio przesianej liczb. Definicja układanki stwierdza, że ​​przesiewanie numeru x przesiewanie powinno rozpocząć się od kwadratu x. Tak więc, podczas przesiewania 3, zacznij od wyeliminowania 9, itp.

Jednak nie rozumiem, jak autor wymyślił to wyrażenie dla startj (mówiąc algebraicznie).

Z uwag układanki:

W ogóle, gdy przesiewania przez n, przesiewanie rozpoczyna się n-squared ponieważ wszystkie poprzednie wielokrotności n zostały przesiane.

Reszta wyrażenia dotyczy odcięcia między liczbami a indeksami sitowymi. W wyrażeniu jest 2, ponieważ wyeliminowaliśmy wszystkie liczby parzyste zanim zaczęliśmy. W wyrażeniu jest 3, ponieważ wektory schematu są oparte na zera, a liczby 0, 1 i 2 nie są częścią sita. Myślę, że 6 to w rzeczywistości kombinacja 2 i 3, ale minęło trochę czasu, odkąd spojrzałem na kod, więc zostawię to tobie, aby dowiedzieć się.

---

Jeśli ktoś może mi pomóc z tym, że byłoby świetnie. Dzięki!

Answer 1

Wydaje mi się, że to wymyśliłem, korzystając z funkcji programistycznej "comments on their website.

Aby ponownie rozwiązać problem, jest zdefiniowany w wykazie jako (+ (* 2 i i) (* 6 i) 3), tj. 2i^2 + 6i + 3.

ja początkowo nie rozumiem, jak to wyrażenie odnoszące się do p - od „przesiewanie” dla wielu p powinno rozpocząć się p^2, pomyślałem, że startj powinno być coś związane z 4i^2 + 12i + 9.

Jednak startj jest indeksem w wektorze v, który zawiera numery nieparzyste zaczynające się od 3. W związku z tym wskaźnik dla p^2 jest rzeczywiście (p^2 - 3)/2.

Poszerzenie równania: (p^2 - 3)/2 = ([4i^2 + 12i + 9] - 3)/2 = 2i^2 + 6i + 3 - która jest wartością startj.

czuję, że może już jaśniej zdefiniować startj jak (quotient (- (* p p) 3) 2), ale mimo to - myślę, że rozwiązuje ona :)

Answer 2

David Seiler: być może nie najczystszy, ale oprócz implementacji podstawowej Sieve, musi także wdrożyć trzy optymalizacje opisane w ćwiczeniu.

Harto: to było moje drugie ćwiczenie. Nadal eksperymentowałem z moim stylem pisania.

Ephemient: prawidłowe.

Zobacz pełniejsze wyjaśnienie w moim komentarzu na Programming Praxis.

EDYCJA: Dodałem dodatkowy komentarz w Programming Praxis. I kiedy faktycznie spojrzałem na kod, myliłem się co do wyprowadzenia liczby 6 w formule; przepraszam, zwodzę cię.