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 ;
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) ;
2 | 3 | 5 | 7 | 9 | 11 | 13 | 15 |
3. Puis on barre tous les multiples stricts de 3 ;
2 | 3 | 5 | 7 | 11 | 13 |
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 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) |
→ |
|
Exercice 1
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) |
→ |
|
Exercice 1
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