Crible d'Ératosthène
Algorithmique classique
Enonce
Retourner la liste de tous les nombres premiers inférieurs ou égaux à n en utilisant le crible d'Ératosthène.
Signature attendue
def crible(n: int) -> list:Exemples
crible(30)→[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]crible(10)→[2, 3, 5, 7]
📖 Rappel de cours
On part d'un tableau de booléens supposant tout premier, puis on raye les multiples de chaque nombre premier trouvé, en commençant à son carré.
⚠ Le piège : Commencer à i² et non à 2i : les multiples plus petits ont déjà été rayés par un facteur inférieur. Le crible est en O(n log log n), bien mieux que tester chaque nombre.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Vérifier si Liste Triée Décroissante
- Exponentiation Rapide
- Suite de Syracuse
- Nombre Parfait
- Coefficients Binomiaux (Pascal)
- Conversion Décimal → Base Quelconque
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.