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.
| Limite | Temps |
| 100 000 | 140ms |
| 1 000 000 | 2.7s |
| 10 000 000 | 41s |
Aucun commentaire:
Enregistrer un commentaire