No Title

IN3S02 : Sujet du TD5bis
ESIEE Engineering, Denis BUREAU, octobre 2011.

Classe Eratosthene

Le crible d'Ératosthène est une méthode pour découvrir les nombres premiers (0 et 1 seront considérés comme non 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 pour une limite de 25 :

début :	/	/	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				23		/
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 un tableau de booléens dont chaque case 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 ci-dessus (on peut vouloir savoir si le nombre aMax est premier ou non). <A>

1. Le constructeur sera défini au point 5. D'ici là, considérons les attributs comme correctement initialisés, et notamment le tableau créé avec la bonne taille. <B>

2. É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.
Attention ! La classe Arrays n’est pas dans le paquetage java.lang … <C>

3.      É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).
Remarque : il est inutile de parcourir TOUS les nombres jusqu'à aMax.
Question : quand peut-on arrêter la boucle principale ?
Contrainte : aucun test de divisibilité, donc rayer directement les multiples (à partir duquel ?).
Question : quand doit-on arrêter la boucle interne ? <D>

4. É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. <D>

5. <E> Écrire un constructeur à un paramètre qui initialise aMax puis qui appelle la procédure prepare.

6. É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. <F>

7. Écrire une procédure affiche qui affiche l'intégralité des nombres premiers figurant dans le tableau, à raison de 10 par ligne (utiliser le caractère de tabulation '\t'). <F>

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
...

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
...