Sieb von Eratosthenes - Primes Python finden ⇐ Python

[Guest]

Nur um zu klären, dies ist kein Hausaufgabenproblem < /p>

Ich wollte Primzahlen für eine mathematische Anwendung finden, die ich baue und stieß auf Sieb von Eratosthenes Ansatz. < /p>

Ich habe eine Implementierung in Python geschrieben. Aber es ist furchtbar langsam. Denn wenn ich alle Primzahlen weniger als 2 Millionen finden möchte. Es dauert> 20 Minuten. (Ich habe es an diesem Punkt gestoppt). Wie kann ich das beschleunigen? < /P>

Code: Select all

def primes_sieve(limit):
limitn = limit+1
primes = range(2, limitn)

for i in primes:
factors = range(i, limitn, i)
for f in factors[1:]:
if f in primes:
primes.remove(f)
return primes

print primes_sieve(2000)
< /code>

 Update: < /strong>
Ich habe in diesem Code profiliert und stellte fest, dass viel Zeit für das Entfernen eines Elements aufgewendet wurde Aus der Liste. Ganz verständlich, wenn man bedenkt, dass es die gesamte Liste (Worst-Case) durchqueren muss, um das Element zu finden und es dann zu entfernen, und dann die Liste neu einstellen (vielleicht geht eine Kopie weiter?). Wie auch immer, ich habe die Liste für Wörterbuch ausgestoßen. Meine neue Implementierung - < /p>

def primes_sieve1(limit):
limitn = limit+1
primes = dict()
for i in range(2, limitn): primes[i] = True

for i in primes:
factors = range(i,limitn, i)
for f in factors[1:]:
primes[f] = False
return [i for i in primes if primes[i]==True]

print primes_sieve1(2000000)