Aide à la compréhension de la mise en œuvre de Sieve of Eratosthenes

Question

C'est ennuyeux, je sais, mais j'ai besoin d'un peu d'aide pour comprendre la mise en œuvre du tamis d'Ératosthène. C'est la solution à 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))))))) 

La partie que je vais avoir du mal avec est startj. Maintenant, je peux voir que p va cycler à travers les numéros impairs à partir de 3, défini comme (+ i i 3). Mais je ne comprends pas la relation entre p et startj, qui est (+ (* 2 i i) (* 6 i) 3).

---

Modifier: Je comprends que l'idée est de sauter les numéros précédemment tamisé. La définition du puzzle stipule que lors du tamisage d'un numéro x, le criblage devrait commencer au carré de x. Donc, lors du tamisage 3, commencez par éliminer 9, etc.

Cependant, ce que je ne comprends pas, c'est comment l'auteur a trouvé cette expression pour startj (algébriquement parlant).

D'après les commentaires du puzzle:

En général, lorsque tamiser par n, tamiser commence à n-carré parce que tous les multiples précédents de n ont déjà été tamisé.

Le reste de l'expression a trait à la référence croisée entre les nombres et les index de tamis. Il y a un 2 dans l'expression parce que nous avons éliminé tous les nombres pairs avant même de commencer. Il y a 3 dans l'expression car les vecteurs Scheme sont basés sur zéro, et les nombres 0, 1 et 2 ne font pas partie du tamis. Je pense que le 6 est en fait une combinaison du 2 et du 3, mais cela fait un moment que j'ai regardé le code, alors je vais vous laisser le soin de le comprendre.

---

Si quelqu'un pouvait me aider, ce serait génial. Merci!

Answer 1

Je pense que je l'ai compris, avec l'aide de programmationpraxis 'comments on their website.

Pour répéter le problème, startj est défini dans la liste comme (+ (* 2 i i) (* 6 i) 3), c'est-à-dire 2i^2 + 6i + 3.

Je ne comprends pas comment d'abord cette expression liée à p - depuis « tamiser » pour un certain nombre p devrait commencer à p^2, je pensais que startj devrait être quelque chose relatif à 4i^2 + 12i + 9.

Cependant, startj est un indice dans le vecteur v, qui contient des nombres impairs à partir de 3. Par conséquent, l'indice est en fait p^2(p^2 - 3)/2.

Extension de l'équation: (p^2 - 3)/2 = ([4i^2 + 12i + 9] - 3)/2 = 2i^2 + 6i + 3 - qui est la valeur de startj.

Je pense qu'il pourrait avoir été plus clair de définir startj comme (quotient (- (* p p) 3) 2), mais de toute façon - je pense que résout :)

Answer 2

David Seiler: peut-être pas le plus clair, mais en plus de mettre en œuvre le tamis de base, il doit également mettre en œuvre les trois optimisations décrites dans l'exercice. Harto: c'était mon deuxième exercice. J'expérimentais toujours avec mon style d'écriture.

Éphémère: correct.

Voir une explication plus complète dans mon commentaire à Programming Praxis.

EDIT: J'ai ajouté un commentaire supplémentaire à Programming Praxis. Et quand j'ai regardé le code, je me suis trompé sur la dérivation du nombre 6 dans la formule; désolé je vous induis en erreur.