Aide compréhension Sieve de la mise en œuvre Eratosthène

Question

Ceci est ennuyeux, je sais, mais je besoin d'un peu d'aide pour comprendre une mise en œuvre de la Sieve d'Eratosthène. Il est la solution ce problème de programmation Praxis .

(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 à se startj. Maintenant, je peux voir que p va être à vélo à travers les nombres 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 de puzzle indique que lorsque tamiser un certain nombre x, Tamiser devrait commencer à la place de x. Donc, quand tamiser 3, commencer par éliminer 9, etc.

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

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 doit faire avec la référence croisée entre les nombres et les indices de tamis. Il y a 2 dans l'expression parce que nous avons éliminé tous les chiffres avant même que nous ayons jamais commencé. Il y a un 3 dans l'expression, car les vecteurs régime sont fondées zéro, et les chiffres 0, 1 et 2 ne font pas partie du tamis. Je pense que le 6 est en fait une combinaison des 2 et 3, mais il a été un moment que je regardais le code, donc je vais laisser à vous comprendre.

---

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

Answer 1

Je pense que je l'ai pensé à elle, avec l'aide de programmingpraxis' commentaires sur leur site .

Pour reformuler le problème, startj est défini dans la liste comme (+ (* 2 i i) (* 6 i) 3), à savoir 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 me suis dit que startj devrait être quelque chose relatif à 4i^2 + 12i + 9

Cependant, startj est un indice dans le v vectoriel, qui contient des nombres impairs à partir de 3. Par conséquent, l'indice p^2 est en fait (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 cela permet de résoudre:)

Answer 2

David Seiler:. Peut-être pas la plus claire, mais en plus de la mise en œuvre du Sieve de base, il doit également mettre en œuvre les trois optimisations décrites dans l'exercice

Harto: qui était mon deuxième exercice. Je continuais à expérimenter avec mon style d'écriture.

Ephemient. Correcte

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

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