|
Autor: mk 06.07.2008 14:27:28 668 |
|
||
| Standard-Algorithmen |
Bauernmultiplikation
quadratische Gleichung
ggt
Bachet
Heron
Potenz
Primfaktorzerlegung
Halbierung
Newton
pi-Bestimmung
Sortieren
Backtracking
|
|
|
Sieb des Eratosthenes |
# -*- coding: iso-8859-1 -*-
# Autor: Klaus Merkert, Datum: 2.6.08
def sieb(n):
P = range(2,n+1) # Liste P = [2,3,4,...,n]
i = 0 # Position der aktuellen Primzahl
p = P[i] # p ist aktuelle Primzahl
while p*p <= n: # 1)
v = 2*p # v ist ein Vielfaches von p, zuerst v=2*p
while v <= P[-1]: # ist v <= letztes Element der Liste P?
if v in P: # ist v überhaupt noch in der Liste?
P.remove(v) # v aus Liste entfernen
v = v+p # zum nächsten möglichen Vielfachen
i = i+1
p = P[i] # nächste (nicht gestrichene) Zahl in der Liste
return P
# 1) Jede nichtprime Zahl <= n muss durch eine Primzahl p teilbar sein, für
# die p*p <= n gilt. Daher muss man nur bis zu dieser Primzahl p die
# Vielfachen streichen.
# Angenommen p1<p2<..<pg sind alle die Primzahlen mit p*p <= n. Sei m <= n
# und nicht prim, dh. pgg>pg ist eine Primzahl mit pgg | m. Also gilt
# m = pgg*f. f ist eine Zahl, die nicht durch p1,...,pg teilbar ist, dh.
# f >= pgg. Damit folgt m >= pgg*pgg > n (letztes > nach Voraussetzung).
# Widerspruch zu m <= n.
if __name__ == '__main__': # wenn Modul als Hauptprogramm, dann Tests
import time
t1 = time.clock()
print sieb(1000)
t2 = time.clock()
print 'Rechenzeit: '+str(t2-t1)+'s'
Die zu streichenden Vielfachen könnte man auch bei v = p*p beginnen lassen. Messungen ergeben aber keine kürzeren Rechenzeiten. Vielleicht hängt das daran, dass *2 und +p leicht im Vergleich zu p*p zu rechnen ist.
