Un nombre premier est un nombre entier naturel qui admet exactement deux diviseurs distincts
entiers et positifs : 1 et lui-même.
Le crible d’Ératosthène permet de déterminer les nombres premiers plus petit qu’un certain
nombre n fixé.
On considère pour cela un tableau tab de nbooléens, initialement tous égaux à True, sauf
tab[0] et tab[1] qui valent False, 0 et 1 n’étant pas des nombres premiers.
On parcourt alors ce tableau de gauche à droite.
Pour chaque indice i :
si tab[i] vaut True : le nombre i est premier et on donne la valeur False à toutes les
cases du tableau dont l’indice est un multiple de i, à partir de 2*i (c’est-à-dire 2*i, 3*i ...).
si tab[i] vaut False : le nombre i n’est pas premier et on n’effectue aucun
changement sur le tableau.
On dispose de la fonction crible, incomplète et donnée ci-dessous, prenant en paramètre un
entier n strictement positif et renvoyant un tableau contenant tous les nombres premiers plus
petits que n.
def crible(n):bksl-nl """bksl-nl Renvoie un tableau contenant tous les nombres premiers plus petitsbksl-nl que nbksl-nl """bksl-nl premiers = []bksl-nl tab = [True] py-str nbksl-nl tab[0], tab[1] = False, Falsebksl-nl for i in range(..., n):bksl-nl if tab[i] == ...:bksl-nl premiers.append(...)bksl-nl for multiple in range(2 py-str i, n, ...):bksl-nl tab[multiple] = ...bksl-nl return premiersbksl-nlbksl-nl# Testsbksl-nlassert crible(40) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]bksl-nlbksl-nlbksl-nldef crible(n):bksl-nl """bksl-nl Renvoie un tableau contenant tous les nombres premiers plus petitsbksl-nl que nbksl-nl """bksl-nl premiers = []bksl-nl tab = [True] py-str nbksl-nl tab[0], tab[1] = False, Falsebksl-nl for i in range(2, n):bksl-nl if tab[i] == True:bksl-nl premiers.append(i)bksl-nl for multiple in range(2 py-str i, n, i):bksl-nl tab[multiple] = Falsebksl-nl return premiersbksl-nlbksl-nlbksl-nlbksl-nlbksl-nl
A la place de la ligne 12 nous aurions pu écrire :
for multiple in [k*i for k in range(2, n) if k*i<n]:
