ESIEE.BureauD.exotd5

IN101 : Sujet de TD supplémentaire
1h, ESIEE Engineering, Denis BUREAU, 2010.

1 Classe Eratosthene

Le crible d'Ératosthène est une méthode pour découvrir les nombres premiers. Il consiste à mettre tous les entiers (inférieurs à une certaine limite) dans une grille, puis à rayer méthodiquement tous les multiples des nombres non encore rayés.
Exemple :

debut:	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
raye 2:	2	3	/	5	/	7	/	9	/	11	/	13	/	15	/	17	/	19	/	21	/	23	/	25
raye 3:	2	3		5		7		/		11		13		/		17		19		/		23		25
raye 5:	2	3		5		7				11		13				17		19				2 3		/

raye 7: ...
On constate alors qu'il ne reste plus que des nombres premiers dans la grille.

En informatique, il est toutefois difficile de "rayer" un nombre. On choisit donc de déclarer (comme attribut de la classe) un tableau de booléens dont la première case ne sera pas utilisée ¹ et dont chaque case suivante représentera le nombre entier correspondant à son indice : si la valeur de la case est true, c'est que l'entier correspondant n'est pas rayé.
Et rayer un nombre signifiera donc passer la case correspondante à false.
Déclarer également un attribut aMax correspondant à la limite évoquée précédemment.

Écrire une procédure initV qui initialise à VRAI les aMax-1 derniers éléments du tableau, pour signifier qu'a priori, tous les nombres entiers (sauf 0 et 1) sont candidats à être premiers.
Écrire une procédure raye qui applique la méthode décrite ci-dessus en mettant FAUX dans chaque case du tableau correspondant à un nombre qu'elle doit "rayer" (inférieur ou égal à aMax).
Contrainte : aucun test de divisibilité.
Remarque : il est inutile de parcourir TOUS les nombres jusqu'à aMax.
Question : quand peut-on arrêter la boucle principale ?
Écrire une procédure prepare qui commencera par créer le tableau de booléens avec la bonne taille en fonction de aMax, puis appellera les procédures initV et raye.
Écrire un constructeur à un paramètre qui initialise aMax puis qui appelle la procédure prepare.
Écrire une fonction booléenne estPremier qui prend en paramètre l'entier à tester et qui détermine si l'entier est premier ou non.
Écrire une procédure affiche qui affiche l'intégralité des nombres premiers figurant dans le tableau, à raison de 10 par ligne (utiliser des tabulations).

Exemple d'affichage :

2	3	5	7	11	13	17	19	23	29
31	37	41	43	47	53	59	61	67	71
73	79	83	89	97	101	103	107	109	113
127	131	137	139	149	151	157	163	167	173
179	181	191	193	197	199	211	223	227	229

...

Notes:

¹ pour ne pas perturber votre réflexion sur cet algorithme non trivial (donc il y aura aMax+1 cases)

File translated from T_EX by T_TH, version 3.74.
On 05 Apr 2011, 10:21.

2	3	5	7	11	13	17	19	23	29
31	37	41	43	47	53	59	61	67	71
73	79	83	89	97	101	103	107	109	113
127	131	137	139	149	151	157	163	167	173
179	181	191	193	197	199	211	223	227	229

2	3	5	7	11	13	17	19	23	29
31	37	41	43	47	53	59	61	67	71
73	79	83	89	97	101	103	107	109	113
127	131	137	139	149	151	157	163	167	173
179	181	191	193	197	199	211	223	227	229

2	3	5	7	11	13	17	19	23	29
31	37	41	43	47	53	59	61	67	71
73	79	83	89	97	101	103	107	109	113
127	131	137	139	149	151	157	163	167	173
179	181	191	193	197	199	211	223	227	229