Crible d’Ératosthène🔗
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #!/usr/bin/env python3
# coding: utf-8
"""
Crible d'Ératosthène.
Source: http://fr.wikibooks.org/wiki/Exemples_de_scripts_Python#Implémentation_du_crible_d'Ératosthène
"""
__author__ = "Yannick Copin <y.copin@ipnl.in2p3.fr>"
# start-sys
# Gestion simplifiée d'un argument entier sur la ligne de commande
import sys
if sys.argv[1:]: # Présence d'au moins un argument sur la ligne de commande
try:
n = int(sys.argv[1]) # Essayer de lire le 1er argument comme un entier
except ValueError:
raise ValueError(f"L'argument {sys.argv[1]!r} n'est pas un entier")
else: # Pas d'argument sur la ligne de commande
n = 101 # Valeur par défaut
# end-sys
# Liste des entiers *potentiellement* premiers. Les nb non premiers
# seront étiquetés par 0 au fur et à mesure.
l = list(range(n + 1)) # <0,...,n>, 0 n'est pas premier
l[1] = 0 # 1 n'est pas premier
i = 2 # Entier à tester
while i**2 <= n: # Inutile de tester jusqu'à n
if l[i] != 0: # Si i n'est pas étiqueté (=0)...
# ...étiqueter tous les multiples de i: de 2 * i à n (inclu) par pas de i
for j in range(2 * i, n + 1, i):
l[j] = 0
# Les 2 lignes précédentes peuvent être fusionnées:
# l[2 * i::i] = [0] * len(l[2 * i::i])
i += 1 # Passer à l'entier à tester suivant
# Afficher la liste des entiers premiers (c-à-d non étiquetés)
print(f"Liste des entiers premiers <= {n} :")
print([i for i in l if i != 0])
|
$ python3 crible.py
Liste des entiers premiers <= 101
[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, 101]
Source: crible.py