Primzahlen mit dem Sieb des Eratosthenes in Python

Mit dem Sieb des Eratosthenes dauert das Berechnen von den Primzahlen 1 – 1.000.000 in Python nicht mal eine Sekunde, ein kleines Wunder, verglichen mit den 50 Sekunden die dasselbe braucht ohne Optimierung. Wer mehr zur Theorie des Algorithmus wissen will, der kann sich den Wikipedia Artikel angucken.

Hier ist der Code zusätzlich mit Psyco optimiert, was die Geschwindigkeit von 0.88 auf auf 0.33 Sekunden verbessert.

# Implementierung des Sieb des Erathostenes
# (Primzahlen Algorithmus)

class Prim_Eratosthenes:

  def __init__(self, anzahlDerPrimzahlen):
    self.anzahl = anzahlDerPrimzahlen
    self.gestrichen = [False] * (self.anzahl)
    self.calculate()
    #self.print_prims()

  def calculate(self):
    i = 2
    while i*i <= self.anzahl:
      if self.gestrichen[i] == False:
        # i ist prim, streiche seine Vielfache
        for j in range(i*i,self.anzahl,i):
          self.gestrichen[j] = True
      i = i + 1 

  def print_prims(self):
   for i in range(1, self.anzahl):
     if self.gestrichen[i] == False:
       print i

if __name__=='__main__':
  import psyco #Speed it up
  psyco.full()
  Prim_Eratosthenes(1000000)