Sieb von Eratosthenes gibt große zusammengesetzte Zahl zurück (was ein Fehler ist)

Question

Ich implementiere das Sieb von Eratosthenes in Python. Sie gibt zerlegbare Zahlen am Ende des Suchbereiches:

def primes_Ero(n=1000): 
    primes = [] 
    a = [True]*(n+1) 
    a[0] = a[1] = False 
    for (i,isprime) in enumerate(a): 
     if isprime: 
      for n in range(i*i,n+1, i):   
       a[n] = False 
      primes.append(i) 
    return primes 

Wenn größere Zahlen verwenden, n ich mit zusammengesetzten Zahlen enden. Ich habe einen Scheck, um zu sehen, welche Zahlen sind zusammengesetzte (verglichen mit einem Brute-Force-Methode),

n Gegeben, was Zahlen sind Composite:

n= 100; [] 
n= 500; [493, 497] 
n= 1000; [961, 989] 
n= 10000; [9701, 9727, 9797, 9853, 9869, 9917, 9943, 9953, 9983, 9991, 9997] 

Was mache ich falsch?

Answer 1

Das Problem ist, diese Zeile:

for n in range(i*i, n+1, i): 

Anfänglich n den Parameterwert (default = 1000) gesetzt ist, aber nach der for-Schleife zum ersten Mal ausführt n i < n < i + n halten wird. Das zweite Mal, wenn die for-Schleife ausgeführt wird, ist fehlerhaft.

Sie sollten eines der von Ihnen verwendeten n s umbenennen. Überlegen Sie, ob Sie ihm einen richtigen Namen wie sieve_size geben sollten, was aussagekräftiger ist, was er tatsächlich tut.

Eine Sache, die ich hervorheben möchte, ist, dass während Ihr Code ist klug Sie sind Änderung der Liste, die Sie iterieren über. Dies wird allgemein als schlechte Praxis angesehen.