Le crible d'Ératosthène

Le crible d'Ératosthène. Le crible d'Ératosthène (IIIe siècle avant notre ère) donne tous les nombres premiers jusqu'à $n$ : on écrit les entiers de $2$ à $n$ ; on garde le plus petit nombre non barré et on barre tous ses multiples ; on recommence avec le suivant non barré.

• Appliquer l'algorithme à la main pour $n=30$.
• Pour $n=30$, à partir de quel nombre peut-on s'arrêter de barrer ? Justifier qu'il suffit, en général, de traiter les nombres $i$ tels que $i\times i\le n$, et de commencer à barrer à $i\times i$.
• Écrire une fonction crible(n) qui renvoie la liste des nombres premiers inférieurs ou égaux à $n$, à l'aide d'une liste de booléens.
• Quelle leçon d'informatique, soulignée dans le cours à propos de la numération de position, retrouve-t-on dans cet algorithme ?