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 2
FONCTION barrer(T,n)
VAR
i, valeur : entier
fin : booléen
i <- 2
fin <- faux
TANT QUE !fin FAIRE
valeur = i*n
SI valeur < len(T) ALORS
T[valeur] <- faux
i++
SINON
fin <- vrai
FIN SI
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 3
FONCTION tab_premiers(T)
VAR
resultat : liste d'entiers
i : entier
POUR i ALLANT DE 2 A len(T) {PAR_PAS_DE 1}
T <- 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
Partie B
Exercice 1
Coder la fonction init_tab(n) de l’exercice 1 puis la tester.
Exercice 1
function init_tab($n){
$T = array();
$T[0] = false;
$T[1] = false;
for ($i = 2; $i < $n; $i++) {
$T[$i] = true;
}
return $T;
}
function main(){
$T = init_tab(15);
var_dump($T);
}
main();
Exercice 2
Coder la fonction barrer(T,p) de l’exercice 2 puis la tester.
Exercice 2
function barrer($T, $n) {
$valeur = 2;
$i = 2;
$fin = false;
while (!$fin) {
$valeur = $i * $n;
if ($valeur < sizeof($T)) {
$T [$valeur] = false;
$i ++;
} else {
$fin = true;
}
}
return $T;
}
function main() {
$T = init_tab(15);
$T = barrer($T,2);
var_dump($T);
}
main ();
Exercice 3
Coder la fonction tab_premiers(T) de l’exercice 3 puis la tester.
Exercice 3
function tab_premiers($T) {
$resultat = array();
for($i = 2; $i < sizeof($T); $i++) {
$T = barrer( $T, $i );
}
for($i = 2; $i < sizeof($T); $i++) {
if ($T[$i] == true) {
$resultat[] = $i;
}
}
return $resultat;
}
function main($argv) {
if (sizeof ( $argv ) == 1) {
echo "Spécifier la taille du tableau !";
exit ( 1 );
}
/* Lecture de la tailler */
$taille = $argv [1];
/* Initialisation du tableau */
$T = init_tab ($taille);
/* Récupération des nombres premiers */
$T = tab_premiers ( $T );
/* Affichage de la réponse */
echo "Voici la liste des nombres premiers jusqu'à ".$taille." : ";
foreach ($T as $valeur){
echo $valeur;
if($valeur != $T[sizeof($T)-1]){
echo ", ";
}
}
echo "\n";
}
main ($argv);
Exécution
# php -f eratosthene.php 15 Voici la liste des nombres premiers jusqu'à 15 : 2, 3, 5, 7, 11, 13 # php -f eratosthene.php 100 Voici la liste des nombres premiers jusqu'à 100 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97