Le fonctionnement d'une boucle for

Hmmm…
C'est jamais bien bon de toucher à l'itérateur (ou l'itéré) dans une boucle for…
Tu n'auras pas ce soucis avec un while

Déjà, modifier une liste en cours d'itération est une mauvaise pratique car risque de donner des comportements inattendus (ça se passera globalement bien si des éléments sont ajoutés en fin de liste, mais si tu essaies d'en insérer au début c'est la cata).

Maintenant, pour ton code en particulier, tu ne modifies pas la liste, tu en crées une nouvelle, à laquelle tu donnes le même nom que la précédente. Sauf que cette nouvelle liste n'a plus rien à voir avec celle utilisée ligne 8, donc n'est pas prise en compte lors de l'itération. La ligne du for (ligne 8) n'est évaluée qu'une fois avant de commencer à itérer, elle ne fait pas partie du corps de la boucle.

La ligne du for n'est évaluée qu'une fois avant de commencer à itérer, elle ne fait pas partie du corps de la boucle.

S'il fallait une preuve de plus que ce qu'Antoine avance est correct, la voici:

1
2
3

for i in range(1, 10):
 print(i)
i+=1

Comportement totalement contre-intuitif assuré pour celui qui, comme moi, réfléchit avant tout en Java, PHP et C++. Mais en y réfléchissant mieux, c'est tout à fait logique étant donné le fonctionnement objet de python.

Par contre python se protège quand même des modifications concurrentes un minimum, tu ne peux pas faire n'importe quoi n'importe comment non plus; et heureusement, le résultat serait sans doute aléatoire. Ce code provoque une erreur par exemple:

1
2
3
4
5

d = { 'a':1, 'b': 2, 'c': 3}
for k in d:
 v = d[k]
 d[k+k]=v+v
 print(k+'='+str(v))

N'écrit jamais ça. Remplace le par ça :

1
2
3

def is_divisor_of(x, y):
    """Return True if y is a divisor of x else return False"""
    return x%y == 0

La structure que tu utilises revient à dire : « si c'est vrai, retourne vrai, si c'est faux, retourne faux », autant retourner directement vrai ou faux. Ta structure appartient au musée des horreurs.

Mon Python est un peu vieux et il y a suffisamment d'autres personnes ici pour les conseils de style, mais en termes d'algorithmique, c'est pas le crible d'Eratosthène que tu as écrit là. L'idée du crible, c'est de dire que pour éliminer tous les multiples de $n$, on met False dans les cases du tableau de $n$ en $n$ (donc on utilise result comme un tableau, avec des accès immédiats, pas en le parcourant avec un for comme si c'était une liste). Là, pour chaque $n$, tu parcours tout le tableau qui reste et pour chaque case tu fais un test is_divisor.

Edit : en plus, ton code a l'air faux : chez moi, il oublie plein de nombres premiers.

Voilà un peu en vrac ton code, une version correcte, un benchmark à l'arrache et les résultats :

 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

#! /usr/bin/env python
import itertools
import time
import sys

def sieve_of_eratosthenes(limit=100):
    """Return every prime number lower than limit in a list"""
    result = range(1, limit)    # Store all the number from 1 to limit
    i = 1
    while i < len(result):
        # Remove the multiple of i
        result = list(filter(lambda x: x % result[i] != 0, result))
        i += 1
    return list(result)

def sieve(limit):
    is_prime = [True] * (limit + 1)
    for i in range(2, limit + 1):
        if is_prime[i]:
            # On peut s'arrêter à sqrt(limit) si on sait la calculer
            for j in range(2 * i, limit + 1, i):
                is_prime[j] = False
    # On garde 0 et 1 parce que la flemme de les enlever
    return list(itertools.compress(range(limit + 1), is_prime))

n = int(sys.argv[1])
x = time.time()
sieve_of_eratosthenes(n)
y = time.time()
sieve(n)
z = time.time()
print("%d %f %f" % (n, y - x, z - y))

1
2

$ ./primes.py 50000
50000 4.733370 0.009205

Pour les maniaques de la microseconde et les tortionnaires de mouche du coin, je précise quand même : il est évidemment possible d'optimiser le code que j'ai écrit (d'ailleurs le compress pour avoir le même format de retour est un peu laid), et je ne serais même pas surpris si quelqu'un arrivait avec une version tunée du code original qui batte la mienne. Je ne cherche ni à faire un concours de qui dure le moins longtemps, ni même à proposer quelque chose d'efficace sinon je ferais pas ça en python mais à montrer pourquoi l'algorithme du PO n'est pas le bon. Ceci étant dit, que ça ne vous empêche pas de jouer aux micro-optimisations, mais moi je m'arrête là

Voici un texte parlant de cette erreur : https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf.

Moi j'aime les drosophiles. En particulier quand je suis invité de façon aussi méprisante à ne pas les torturer. :}

Blague à part, le code d'Eusèbe peut être rendu plus concis et intuitif en remplaçant la seconde boucle par une slice.

Et accessoirement plus rapide, même si ça n'a qu'un intérêt purement académique sur cette fonction.

1
2
3
4
5
6
7

def sieve(limit):
    is_prime = [True] * (limit + 1)
    false = [False] * (limit + 1)
    for i in range(2, limit + 1):
        if is_prime[i]:
            is_prime[2*i::i] = false[2*i::i]
    return list(itertools.compress(range(limit + 1), is_prime))

C'était en réaction à :