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

Exercice 1

FONCTION code_mot_chiffre(mot)
VAR
   resultat : liste d'entiers
   trouve: booléen
   i, j : entier
   j <- 0

   POUR TOUT j DE mot FAIRE
      i <- 0
      trouve <- faux
      TANT QUE !trouve
         SI alphabet[i] = mot[j]
            resultat[j] <- alphabet[mot[j]]
            trouve <- vrai
         FIN SI
         i++
      FIN TANT QUE
   FIN POUR

   RETOURNER resultat
FIN FONCTION