Crible

Voici un exemple du Crible d'Ératosthène . Il s'agit de trouver tous les nombres premiers inférieur à 100. On va commencer par construire une liste des 100 premiers entiers.

Ensuite on va retirer les multiples de 2, puis de 3, puis du premier nombre restant, c'est à dire 5, ...

Par définition à chaque fois le premier nombre suivant dans la liste est un entier.

Ce programme n'est pas optimisé, puisqu'à partir de 10=100−−−√ $10=\sqrt{100}$  il est évident qu'il n'y plus aucun entier à enlever.

L=[]
for i in range(2,100):
    L.append(i)
print(L)
rang=0 # rang du dernier nombre premier
while rang<len(L):
    premier=L[rang]
    nombre=premier+premier
    while nombre<100:
        if nombre in L:
            L.remove(nombre)
        nombre=nombre+premier
    rang=rang+1
    print(L,rang,premier)

Exercice 1 : 

Calculer la somme des nombres premiers inférieurs à 1 000.

Exercice 2 :  

Optimiser le programme pour calculer la somme des nombres premiers inférieurs à 1 000 000.

Merci pour la planète.