[Python-de] Primzahlenberechnung, Effiziente Speicherung

Robert Heumüller robert at joshavg.de
Mo Jan 26 11:26:07 UTC 2009


Hallo zusammen!

Da dies mein erster Kontakt mit einer Mailingliste ist, möchte ich euch
bitten mir nachzusehen, dass ich mit der Arbeitsweise noch nicht ganz
vertraut bin. 
Nun zu meiner Frage, bzw. zu meinem Problem:

Ich habe ein Programm geschrieben, dass mir die ersten n Primzahlen
ausrechnet und dies durch verschiedene Maßnahmen optimiert, welche die
Rechenzeit stark verkürzen. Beispielsweise genügt es, wenn man die zu
überprüfende Zahl auf Teilbarkeit durch alle ungeraden Zahlen von 3 bis
zur Quadratwurzel der Zahl überprüft, um zu ermitteln, ob es sich um
eine Primzahl handelt. Dieses Programm benötigt zur Errechnung der
ersten 10.000 Primzahlen auf meinem Rechner geschätzt ca. 2-3 Sekunden.
Nun lässt sich das Programm jedoch noch weiter optimieren, denn
theoretisch muss man nicht auf Teilbarkeit durch alle ungeraden Zahlen
prüfen, sondern nur durch Teilbarkeit durch die vorherigen Primzahlen.
Hierzu ist es jedoch notwendig die errechneten Primzahlen in einer Liste
zu speichern. Die Vorteile der Listen dynamischer Länge, die es in
Python gibt liegen auf der Hand, jedoch sind sie in Ihrer Anwendung
leider sehr langsam, da das Programm, wenn auf das n'te Element der
Liste zugegriffen werden soll, zuerst alle Elemente von 0 bis n-1
durchlaufen muss, um zum Element n zu gelangen. Bei einer Liste der
Länge 10.000 bedeutet dies einen großen Zeitaufwand. Das Programm, das
vorher 2-3 Sekunden benötigte brauch nun, in der mathematisch
optimierten Form, fast 20 Sekunden. Gibt es eine Möglichkeit Listen in
Python zu erstellen, auf welche schneller zugegriffen werden kann? In
vielen anderen Programmiersprachen (java, c++, etc.) kann man ja
zusätzlich zu den dynamischen Listen, Vektoren auch Listen einer
vordefinierten Länge anlegen, die wesentlich schneller verarbeitet
werden können, weil der Speicherort von jedem Element nach der
Erstellung feststeht. Gibt es in Python auch eine Möglichkeit dies zu
realisieren?

Vielen Dank für eure Hilfe!

Hier habt ihr nochmal den derzeitigen Programmcode des
Primzahlenrechners (könnte ich ihn auch als Anlage beilegen? 

[code]
import math


anzahl = int(raw_input("Geben Sie die Anzahl der zu errechnenden
Primzahlen an: "))

zaehler = 2
pruefen = 5	
gefunden = [2,3]
darstell = ""

while zaehler < anzahl:
	
	istprim = True
	
	for i in gefunden:
		if (pruefen % i == 0) and (i<(math.sqrt(pruefen)+1)):
			istprim = False
			break
	
	if istprim == True:
		gefunden.append(pruefen)
		zaehler += 1
		
	pruefen +=2
	
for i in range(1,len(gefunden)):
	if (i+1)%10 > 0:
		darstell += str(gefunden[i]) + " "
	else:
		darstell += str(gefunden[i]) + " "
		print darstell
		darstell = ""
[/code]
-------------- nächster Teil --------------
Ein Dateianhang mit HTML-Daten wurde abgetrennt...
URL: <http://python.net/pipermail/python-de/attachments/20090126/6bab14d1/attachment.htm>


Mehr Informationen über die Mailingliste python-de