Php algo td5

Introduction

On cherche à trouver tous les nombres premiers inférieurs à un entier n fixé. L’algorithme du crible d’Ératosthène consiste à barrer, dans la liste de 0 à n, tous les nombres qui ne sont pas premiers. Si l’on cherche tous les nombres premiers inférieurs à 15, l’algorithme procède de la manière suivante :

1. On barre les entiers 0 et 1 qui ne sont pas premiers ;

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

2. Puis on barre tous les multiples stricts de 2, (2 non compris) ;

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

3. Puis on barre tous les multiples stricts de 3 ;

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

4. Etc...

La méthode choisie ici consistera à mettre « false » pour une case barrée et « true » sinon. On utilise un tableau de booléens que l’on initialise ainsi : 1. On barre les entiers 0 et 1 qui ne sont pas premiers ;

false

false

true

true

true

true

true

true

true

true

true

true

true

true

true

true

TAB[0]=false et TAB[1]=false car 0 et 1 ne sont pas premier, et on suppose au début que tous les autres nombres de 2 à 20 sont premiers. A la fin de l’algorithme, seuls les éléments d’indice premiers sont à « true », tous les autres sont passés à « false » (ce qui revient à les barrer).