Le problème
Cette très ancienne méthode permet la détermination de tous les nombres premiers
inférieurs à une valeur donnée. La méthode manuelle consiste à dresser la liste de
tous les entiers entre 1 et n et à y "rayer" tous les nombres multiples d'autres
entiers.
Plus précisément, l'algorithme peut être décrit de la manière suivante :
- rayer le 1,
- rechercher, à partir du dernier nombre premier considéré, le premier nombre non rayé
qui est forcement premier (demander la démonstration à votre professeur de maths
préféré mais ce n'est pas bien compliqué). Ce nombre devient alors le dernier nombre
premier et on raye tous ses multiples,
- recommencer l'opération 2 jusqu'à ce que le nombre premier considéré soit supérieur
à la racine carrée de n. On peut alors montrer que tous les nombres non premiers
ont été rayés de la liste.
Démonstration simple :
- Si n n'est pas premier alors il existe p et q strictement compris entre 1 et n tels que n = p * q
- l'un des deux est forcément plus petit que l'autre, disons p < q,
- multiplions à droite et à gauche par p, nous obtenons p^2 < p*q donc p^2 < n donc p < racine(n)
- donc si n n'est pas premier alors ces diviseurs sont < racine(n)
Programmation
Quelques indications :
- l'énoncé semble suggérer l'utilisation d'un tableau d'entiers mais ce tableau est
inutile puisque les entiers de 1 à n sont bien connus. Par contre, il semble raisonnable
de disposer d'un tableau indiquant pour chaque entier s'il a été rayé ou non. Un
tableau de n "booléens" (entiers en C) s'impose,
- le nombre n est demandé à 1'utilisateur mais ne devra pas excéder la taille prévue
pour le tableau de "booléens",
- l'algorithme informatique est le suivant
- le tableau de booléens sera initialisé à "false",
- commencer l'itération avec une variable prem valant 1,
- rechercher à partir de prem le premier entier non rayé sans toutefois dépasser
la valeur limite n.
- rayer tous les multiples de prem dans le tableau,
- répéter l'opération jusqu'à ce que la valeur de prem, soit supérieure à la
racine carrée de n.
- Vous écrirez 3 procédures ou fonctions
- une d'initialisation du tableau de "booléens",
- une de passage du crible,
- une d'affichage du résultat.