h1

Primzahlen mit dem Sieb des Eratosthenes in Python

August 7, 2008

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)

2 Kommentare

  1. […] Sieb des Eratosthenes Python LinkHallo Stefan Birkner, sie haben den von mir hinzugefügten Link zu https://codecocktail.wordpress.com/2008/08/07/primzahlen-mit-dem-sieb-des-eratosthenes-in-python/ bei dem Artikel zum Sieb des Eratosthenes entfernt. Ich will mich nicht darüber beschweren, denn […]


  2. […] Ich habe den Code hier bewusst klar und einfach gehalten, es sind also durchaus noch Optimierungen möglich, z.B. indem man mit einer Liste aus Boolean-Werten und ohne die eingebaute if-Abfrage arbeitet. Ein Beispiel findet sich z.B. im codecocktail-Blog. […]



Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: