Multiples et crible d'Ératosthène
Dans ce cours, on joue avec les multiples : d'abord un petit jeu célèbre chez les programmeurs, puis un algorithme antique et très efficace.
Le Fizz Buzz
La règle : compter de 1 à 15, mais dire « Fizz » à la place des multiples de 3, « Buzz » à la place des multiples de 5, et « FizzBuzz » pour les multiples des deux.
Un nombre est multiple de 3 quand le reste de sa division par 3 est nul : n mod 3 = 0.
pour i de 1 à 15
si i mod 3 = 0 et i mod 5 = 0 alors
affiche 'FizzBuzz'
sinon si i mod 3 = 0 alors
affiche 'Fizz'
sinon si i mod 5 = 0 alors
affiche 'Buzz'
sinon
affiche i
fin si
fin pour
L'ordre des tests compte. Si on testait d'abord i mod 3 = 0, le nombre 15 afficherait « Fizz » et le cas « FizzBuzz » ne serait jamais atteint. On commence toujours par le cas le plus précis.
Question : Que doit afficher le programme pour le nombre 10 ? — Buzz. 10 est un multiple de 5, mais pas de 3 : c'est « Buzz ».
Chercher tous les nombres premiers
Pour trouver tous les nombres premiers jusqu'à 50, on pourrait tester chaque nombre un par un. Le savant grec Ératosthène a eu une idée plus rapide, il y a 2 200 ans : plutôt que chercher les nombres premiers, éliminer ceux qui ne le sont pas.
- On écrit tous les nombres de 2 à 50.
- On prend le premier nombre non barré (2) : il est premier. On barre tous ses multiples (4, 6, 8...).
- On passe au nombre non barré suivant (3) : il est premier. On barre ses multiples (6, 9, 12...).
- Et ainsi de suite.
Les nombres qui restent à la fin sont les nombres premiers. On appelle cette méthode un crible, comme une passoire qui ne laisse passer que les nombres premiers.
Le crible en CoddyRun
On utilise un tableau de booléens : la case i dit si le nombre i est encore « non barré ».
limite est un nombre vaut 50
// au départ, tous les nombres sont supposés premiers
nonBarre est un tableau
pour i de 0 à limite
nonBarre ajoute vrai
fin pour
nonBarre[0] vaut faux
nonBarre[1] vaut faux
// barrer les multiples de chaque nombre premier
pour i de 2 à limite
si nonBarre[i] alors
pour j de i * 2 à limite pas i
nonBarre[j] vaut faux
fin pour
fin si
fin pour
// afficher ceux qui restent
trouves est un tableau
pour i de 2 à limite
si nonBarre[i] alors
trouves ajoute i
fin si
fin pour
affiche joindre(trouves, ' ')
affiche longueur(trouves) + ' nombres premiers jusqu’à ' + limite
Le programme trouve les 15 nombres premiers jusqu'à 50 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 et 47.
La boucle intérieure pour j de i * 2 à limite pas i saute de i en i : pour i = 3, elle visite 6, 9, 12, 15... exactement les multiples de 3.
Pourquoi c'est rapide
Le crible ne fait aucune division : il se contente de sauter de multiple en multiple. Pour trouver tous les nombres premiers jusqu'à un million, il est des centaines de fois plus rapide que de tester chaque nombre séparément.
En échange, il utilise de la mémoire : un tableau d'un million de cases. C'est un compromis classique en informatique : on gagne du temps en dépensant de la place.
Change limite pour 1000 et relance : le programme répond tout aussi vite, et trouve 168 nombres premiers.
En résumé
n mod k = 0 teste si n est un multiple de k.- Dans une suite de
sinon si, on teste le cas le plus précis en premier. - Le crible d'Ératosthène élimine les multiples au lieu de tester chaque nombre.
- Un tableau de booléens peut servir de « liste de cases à cocher ».
- Gagner du temps coûte souvent de la mémoire, et inversement.
