tete du loic

 Loïc YON [KIUX]

  • Enseignant-chercheur
  • Référent Formation Continue
  • Responsable des contrats pros ingénieur
  • Référent entrepreneuriat
  • Responsable de la filière F2 ingénieur
  • Secouriste Sauveteur du Travail
mail
loic.yon@isima.fr
phone
(+33 / 0) 4 73 40 50 42
location_on
ISIMA
  • twitter
  • linkedin
  • viadeo

[C] Examen 2020

Le crible d’Ératosthène

Le crible d’Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné n. L’algorithme procède par élimination : il s’agit de trouver le premier entier non supprimé puis supprimer tous ses multiples, à l’exception de lui même. À la fin, il ne restera que les nombres premiers. Par exemple, pour n = 20, on obtient à la fin l’ensemble des nombres premiers compris entre 2 et 19.

On va utiliser un tableau de booléens (VRAI/1 ou FAUX/0) pour l'implémentation de cet algorithme. On initialise le tableau à VRAI sauf pour les positions 0 et 1 car ni 0 ni 1 ne sont premiers.

012345678910111213141516171819
FFVVVVVVVVVVVVVVVVVV

On cherche la position de la première case à VRAI : 2. On met à FAUX tous les multiples de 2 strictement supérieurs à 2.

012345678910111213141516171819
FFVVFVFVFVFVFVFVFVFV

On cherche la position de la première case à VRAI après 2 : 3. On met à FAUX tous les multiples de 3 strictement supérieurs à 3.

012345678910111213141516171819
FFVVFVFVFFFVFVFFFVFV

On continue jusqu’à ce qu’il n’y ait plus de prochaine case à VRAI. Le tableau est donc complet : chaque position à VRAI est un nombre premier.

Notes sur le travail à réaliser

L'affiche de la liste des nombres se fait avec un seul espace entre les nombres. La chaine n'a pas d'espace à la fin.