Dernière version du 19 avril 2014 à 19:25

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

Solution

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

Solution

FONCTION barrer(T,p)
VAR
   i, valeur : entier
   fin : booléen
   i <- 2
   fin <- faux

   TANT QUE !fin FAIRE
      valeur = i*p
      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)

→

2	3	5	7	11	13

Solution

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.append(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.

Solution

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.

Solution

function barrer($T, $p) {
   $valeur = 2;
   $i = 2;
   $fin = false;
   while (!$fin) {
      $valeur = $i * $p;
      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.

Solution

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() {
   $T = init_tab(15);
   $T = tab_premiers($T);
   var_dump($T);
}

main ($argv);

Exercice 4

Écrire la fonction principale qui prend en paramètre la taille de la liste et qui affiche les nombres premiers.

Solution

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