Pourquoi mon tamis d'Erasthotenes ne fonctionne-t-il pas? Python 3

Question

Ceci est mon code. J'essaye de faire un tamis efficace mais simple d'Erasthotenes mais quand je cours le programme il continue juste de renvoyer des nombres entiers, aussi grand que j'ai mis la gamme. Ceci est en python 3.

lyst = [] 
for i in range(2, 100): 
    print(i) 
    lyst.append(i) 
count = 2 
index = 1 
for x in lyst: 
    print(str(index) + " : " + str(count)) 
    if x%count == 0 and x != count: 
     lyst.remove(x) #removing all multiples of count 
    if max(lyst) == count: #breaks loop if count is the largest prime 
     break 
    else: 
     count = lyst[lyst.index(count)+1] #turns count into next prime 
    index += 1 #this is just for me to track how many primes i've found 

Answer 1

Cela devrait le faire ... un coup d'oeil à la boucle intérieure qui élimine les multiples:

lyst = [] 
max = 100 # because ... you know, variables. ... 
for i in range(2, max): 
    lyst.append(i) 
count = 2 
index = 1 
for x in lyst: 
    print(str(index) + " : " + str(x)) # x is a prime number, so print it 
    for y in lyst: 
     if y>x and y%x == 0: 
      lyst.remove(y) 

    index += 1 #this is just for me to track how many primes i've found 
print(index) # how many did we find 

Answer 2

C'est un mélange de votre code et le wikipedia description:

n = 100 
lyst = range(2, n) 
for p in lyst: 
    if not p: 
     continue 
    for i in range(2*p,n,p): 
     lyst[i-2] = None 
print [p for p in lyst if p] 
#=> [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] 

Answer 3

la valeur de x et nombre aura toujours la même valeur:

• ils commencent comme ça avec la valeur 2
• pour cette raison que le remove ne sera pas exécuté
• à la fin de l'itération comptage sera la valeur suivante de la liste, ce qui est exactement ce x sera au début de la prochaine itération

Conclusion: ils ont la même valeur au début de chaque itération, et par conséquent leLa conditionn'est jamais satisfaite. Deuxièmement, le tamis des Erasthotenes n'est pas supposé retirer les éléments du tamis, mais marquer certaines valeurs comme non-prime. Son pouvoir est de garder les valeurs à leur index d'origine, donc .remove() n'est pas vraiment supposé se produire dans un algorithme de tamis simple.

Pour l'inspiration sur la recherche d'une mise en œuvre correcte, vous pouvez regarder plusieurs réponses:

• Sieve of Eratosthenes - Finding Primes Python
• A Fast Prime Number Sieve in Python
• Python- Sieve of Eratosthenes- Compact Python
• ... et beaucoup plus.