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

Partie A

Exercice 1

Écrire une fonction init_tab(n) dont le paramètre est un entier n. Cette fonction renvoie une liste T de taille n représentant les booléens « false », « false » puis « true ».

Exemple :

init_tab(15)

→

false false true true true true true true true true true true true true true true

Exercice 1

FONCTION init_tab(n)
VAR
   T : liste de booléens
   i : entier
   
   T[0] <- faux
   T[1] <- faux

   POUR i ALLANT DE 2 A n {PAR_PAS_DE 1}
      T[n] <- vrai
   FIN POUR

   RETOURNER T
FIN FONCTION

Exercice 2

Écrire une fonction barrer(T,p), dont les paramètres sont une liste T et p un nombre premier. Cette fonction remplace true par false dans la liste T lorsque l’indice de T est un multiple de p puis renvoie T.

Exemple :

barrer(T, 2)

→

false false true true false true false true false true false true false true false true

Exercice 2

FONCTION barrer(T,n)
VAR
   i, valeur : entier
   i <- 2

   TANT QUE valeur < len(T) FAIRE
      valeur = i*n
      T[valeur] <- faux
      i++
   FIN TANT QUE

   RETOURNER T
FIN FONCTION

Exercice 3

Écrire une fonction tab_premiers(T) qui crée la liste des nombres premiers cherchés et qui renvoie cette liste.

Exemple :

tab_premiers(T)

→

2 3 5 7 11 13

Exercice 3

FONCTION tab_premiers(T)
VAR
   resultat : liste d'entiers
   i : entier
   POUR i ALLANT DE 2 A len(T) {PAR_PAS_DE 1}
      barrer(T, i)
   FIN POUR
   POUR i ALLANT DE 2 A len(T) {PAR_PAS_DE 1}
      SI T[i] = vrai ALORS
         resultat[] <- i
      FIN SI
   FIN POUR
   RETOURNER resultat
FIN FONCTION