erreur de valeur pour résoudre un problème d'eratosthenes en python

Question

Voici ma version du crible d'Eratosthène pour trouver des nombres premiers jusqu'à une limite n. Je me sens comme ça devrait fonctionner, mais je reçois une erreur et je ne comprends pas vraiment pourquoi:

mylist.remove(i) 
ValueError: list.remove(x): x not in list 

Pourquoi faut-il mentionner x?

Voici le code:

def number_list(n): 

    mylist = [] 
    for i in range(2,n+1): 
     mylist.append(i) 
    return mylist 


def sieve(): 

    n = eval(input("What is the maximum limit? ")) 
    mylist = number_list(n) 

    primes = [] 

    for i in mylist: 
     p = mylist.pop(0) 
     primes.append(p) 
     if i % p == 0: 
      mylist.remove(i) 
    return primes 

Answer 1

Vous modifiez mylist en l'itérant. Cela donnera des résultats étranges. Au cours de la première exécution de votre boucle, i sera affecté au premier élément de votre liste, c'est-à-dire 2. Ensuite, la déclaration

p = mylist.pop(0) 

supprime cet élément très depuis le début de la liste, et p est également mis à 2. Ensuite, votre vérification i % p == 0 donnera True, et vous essayez de supprimer i de la liste, mais il est déjà parti, entraînant le message d'erreur que vous avez cité.

La logique complète de cette boucle semble être rompue. Pour chaque prime que vous rencontrez, vous devez supprimer tous les multiples de ce premier dans la liste. Vous avez généralement besoin de deux boucles imbriquées pour y parvenir.

En outre, votre fonction

def number_list(n): 
    mylist = [] 
    for i in range(2,n+1): 
     mylist.append(i) 
    return mylist 

est équivalent à

def number_list(n): 
    return range(2, n + 1) 

vous dire pas besoin de cette fonction à tous, il suffit d'utiliser range(2, n + 1) à la place.

Answer 2

Je ne sais pas, mais je pense que vous ne devriez pas modifier la liste vous itérer.
C'est interdit en perl, peut-être que python est similaire dans ce cas.

Une autre chose est que j'utiliserais des générateurs pour votre liste de tous les articles.
L'approche que vous utilisez va souffler la mémoire pour les grands n '.

Answer 3

Le spécifique mentionné ici est réellement i (comme vu sur la ligne ci-dessus). Normalement, les Stacktraces vous donnent également des numéros de ligne, il devrait donc être facile de déboguer en sachant cela. De toute façon, le problème ici est que vous essayez de supprimer certains éléments plus d'une fois. Vous pouvez facilement le corriger avec un if i in mylist mais je vous recommande de regarder une implémentation complète du tamis pour obtenir une version plus rapide/plus optimisée (et plus important encore, de travail). Cela pourrait vous donner un aperçu supplémentaire du fonctionnement de Python.

Answer 4

Voici un code de travail pour le tamis d'Ératosthène. L'objet range doit être créé dans une liste car nous devons supprimer des éléments.

def all_primes_to(n): 
    numbers = list(range(2,n+1)) 
    primes = [] 
    while numbers: 
     prime = numbers.pop(0) 
     primes.append(prime) 
     remove_multiples(numbers, prime) 
    return primes 

def remove_multiples(lst, x): 
    length = len(lst) 
    i = 0 
    while i < length: 
     if lst[i] % x == 0: 
      del lst[i] 
      length -= 1 
     i += 1