jeudi 22 septembre 2011

Le crible en détail, partie 2

Continuons donc à décortiquer le programme.

La fonction principale de notre crible contient la sous-fonction do_sieve, qui permet une fois de plus de devenir tail recursive, ou à récursion terminale en bon français.

Elle prend comme paramètres l'entier courant à tester, l'ensemble des multiples des nombres premiers précédents, et la liste courante des nombres premiers. À partir de là, c'est tout bête: l'on retire le premier élément de nos multiples, et on le compare à l'entier à tester. S'ils sont égaux, notre entier courant est un multiple, donc non premier, l'on ré-appelle donc notre fonction récursive avec l'entier suivant. Si ce n'est pas l'entier à tester, on a trouvé un nombre premier! L'on ajoute tous ses multiples à la liste des multiples, l'on rajoute l'entier à la liste de nos nombres premiers, et l'on appelle la fonction récursivement. Et bien sûr, puisqu'il faut bien sortir un jour de la récursion, n'oublions pas notre condition de sortie: lorsque l'entier courant atteint le maximum passé en paramètre de la fonction principale, l'on retourne nos nombres premiers.

Notez l'optimisation qui consiste à zapper les multiples de 2: l'on démarre à 3, et l'on passe de 2 en 2 pour l'entier courant et pour le calcul des multiples.

Voici une indication des performances. Loin des meilleurs résultats impératifs, mais tout à fait utilisables.




LimiteTemps
100 000140ms
1 000 0002.7s
10 000 00041s

Aucun commentaire: