01 /**
02 * Le crible d'Eratosthene. Il calcule les nombres premiers suivant
03 * l'algorithme dit du crible d'Eratosthene. Les entiers sont stockes dans un
04 * ensemble.
05 *
06 * @author <a href="mailto:cregut@enseeiht.fr">Xavier Cregut</a>
07 * @version 1.0
08 */
09 public class CribleEntier {
10
11 // L'ensemble des nombres est vide entre deux utilisations du crible !
12 //
13 //@ private invariant nombres.estVide();
14
15 /** L'ensemble utilise par le crible */
16 private EnsembleEntierTab nombres;
17
18 /** Fournir l'ensemble ens a utiliser
19 */
20 //@ requires ens.estVide();
21 // ensures nombres == ens; // Ne peut pas etre exprime comme une
22 // postcondition car fait reference a un attribut prive !
23 public CribleEntier(EnsembleEntierTab ens)
24 {
25 nombres = ens;
26 }
27
28 /** Cribler les entiers de 2 a max par l'algorithme d'Eratosthene.
29 * Les nombres premiers sont affiches a l'ecran.
30 * L'ensemble nombres est utilise pour conserver les entiers.
31 */
32 public void cribler(int max)
33 {
34 // construire le nombres des entiers de 2 a max
35 for(int nb = 2; nb <= max; nb++) {
36 nombres.ajouter(nb);
37 }
38
39 // afficher les nombres premiers (on suppose 1 premier !)
40 System.out.print("Nombres premiers : " + 1);
41 while(!nombres.estVide()) {
42 // determiner le nombre premier suivant
43 int premier = nombres.getMin();
44
45 // afficher le nombre premier
46 System.out.print(", " + premier);
47 System.out.flush();
48
49 // supprimer les multiples de premier
50 for(int multiple = premier; multiple <= max; multiple +=premier) {
51 nombres.oter(multiple);
52 }
53 }
54 System.out.println();
55 }
56 }
|