Das deutsche Python-Forum

Hi ich bin ein Anfänger und hab mal ein Programm geschrieben, welches Primzahlen berechnet. Allerdings ist es noch sehr langsam. Aber ich check diese lamba Funktion nicht die anderswo vorgeschlagen wurde

mein Quelltext

Code: Alles auswählen

#!/usr/bin/python
# -*- coding: utf-8 -*-
import pickle

anfang=raw_input('Geben Sie den Start ein!')
grenze=raw_input('Geben Sie die Höchstgrenze ein!')
grenze=int(grenze)
i=int(anfang)
if (i==1 ):
	i=2

mylist=[]
while (i<=grenze):
	primzahl=True
	y=2
	while(y<i):
		rest = i%y
		if rest ==0:
			primzahl=False			
			break
		if (y/2>i):
			break		
		y=y+1
	if (primzahl == True):
		print str(i) +' ist eine Primzahl!'
		mylist.append(str(i)+', ')
	
	i=i+1

fd=open("listeprimzahlen", "w")
   
	
pickle.dump(mylist, fd)
fd.close()	
anzahl= len(mylist)
print 'Es wurden '+str(anzahl)+' Primzahlen gefunden!'

Danke für eure Hilfe![/quote]

Tipp: Schau Dir mal das Sieb des Eratosthenes an. Das ist für grössere Wertebereiche immernoch die effektivste Methode zum Finden von Primzahlen.

Du kannst auch Deinen Brute-Force-Ansatz noch weiter optimieren, überlege Dir einfach mal, bis zu welcher Zahl Du einen Teilertest machen mußt, ob eine weitere Testung im Falle primzahl=False noch sinnvoll ist und welche Teiler überhaupt getestet werden müssen.

Edit: fd steht in der Regel für einen file descriptor, Du nutzt hier aber ein file object. Ist für die Lesbarkeit nicht von Vorteil.

r00t hat geschrieben:Aber ich check diese lamba Funktion nicht die anderswo vorgeschlagen wurde

lambda erzeugt eine anonyme Funktion, d.h. eine Funktion, die an keinen Namen gebunden ist.
Allerdings kann man die schlicht einer Variablen zuweisen, z.B. so:

Code: Alles auswählen

x = lambda y: y
#Aufruf: x(y)

So ist die anonyme Funktion nicht mehr anonym.

Man kann solche Funktionen benutzen, um sie als Argumente an andere Funktionen zu übergeben, z.B. an map:

Code: Alles auswählen

map(lambda x: x ** 2, range(0, 10))

Da ist nirgendwo eine lambda Funktion. Die Klammern bei if, while usw kannst du weglassen, um Operatoren (=, ==, ..) sollte man besser Leerzeichen setzen. Statt "y = y <operator>" zu schreiben kannst du "y <operator>=" schreiben, also zb "y += 1". Statt Strings mit + zusammenzusetzen solltest du besser String formatting ufbenutzen, siehe Tutorial auf docs.python.org. Und etwas in einer if Abfrage nochmal auf Gleichheit mit True zu testen ist unnötig, da if sowieso den Wahrheitswert überprüft, du kannst also "if primzahl:" schreiben.

jerch hat geschrieben:Tipp: Schau Dir mal das Sieb des Eratosthenes an. Das ist für grössere Wertebereiche immernoch die effektivste Methode zum Finden von Primzahlen.

<klugscheiß>Es gibt effektivere Siebverfahren als das des Eratosthenes</klugscheiß>

ABER: Das Sieb des Eratothenes ist trotzdem höchst empfehlenswert. Eine bestechend simple Idee mit hohem Wirkungsgrad. Sich damit zu beschäftigen lohnt sich auf jeden Fall.

Habs jetzt so verbessert dass er nur noch durch die errechneten Primzahlen teilt also quasi des Sieb...

Code: Alles auswählen

#!/usr/bin/python
# -*- coding: utf-8 -*-
import pickle
import math


grenze=raw_input('Geben Sie die Höchstgrenze ein!')
grenze=int(grenze)
i=10


mylist=[2,3,5,7]

while (i<=grenze):
	primzahl=True
	Nr=0
	y=mylist[Nr]
	wurzel=math.sqrt(i)
	while(y<=wurzel):
		rest = i%y
		if rest ==0:
			primzahl=False
			break
		Nr=Nr+1
		y=mylist[Nr]
	
		
		
				
		
	if (primzahl == True):
		print str(i) +' ist eine Primzahl!'
		mylist.append(i)
	i=i+1	
		

	
anzahl= len(mylist)
print 'Es wurden '+str(anzahl)+' Primzahlen gefunden!'

Der einzige Nachteil ist jetzt eben,dass man nicht mehr sagen kann nur noch die Primzahlen zwischen 10 und 100 weil man ja die Primzahlen davor zum teilen braucht. Aber trotzdem vielen Dank für eure Hilfe!!!!

r00t hat geschrieben:Der einzige Nachteil ist jetzt eben,dass man nicht mehr sagen kann nur noch die Primzahlen zwischen 10 und 100 weil man ja die Primzahlen davor zum teilen braucht. Aber trotzdem vielen Dank für eure Hilfe!!!!

Das klingt so, als wärest du jetzt fertig mit deinem Programm?
Eigentlich fängt es doch gerade erst an. Wenn du da noch ein bisschen dran bleibst, kannst du
a) mit etwas Unterstützung aus dem Forum lernen, wie man ein anständiges Python-Programm schreibt
b) ein Primzahlprogramm schreiben, das dir am Ende wirklich Freude macht, weil es einige zig tausend Primzahlen in nullkommanix berechnet.

Es gibt effektivere Siebverfahren als das des Eratosthenes

Klar, ich versteh die allerdings eher als "durchoptimierte" Versionen des Siebes des cleveren Griechens.

@ r00t:
Vergleich doch mal Deinen Algorithmus mit dem des Siebes (das Bild in der Wikipedia ist sehr anschaulich) im Hinblick auf die Laufzeit. Vllt. fällt Dir da was auf (mußt ja nicht gleich eine Komplexitätsanalyse machen, zähl einfach mal die notwendigen Schleifendurchläufe für unterschiedliche Wertebereiche).
Hast Du das durchdrungen, versuchs mal in Code umzusetzen, selbst da gibts dann noch viel Optimierungsspielraum (Codeästhetik ist nicht gleich Laufzeitoptimierung).
Und zu guter Letzt gibts im Algorithmus auch dann noch Verbesserungsmöglichkeiten, ich sag nur mal Atkin

Viel Spaß beim Tüfteln, Jerch

jerch hat geschrieben:
Es gibt effektivere Siebverfahren als das des Eratosthenes
Klar, ich versteh die allerdings eher als "durchoptimierte" Versionen des Siebes des cleveren Griechens.

Ja, das kann man so sehen.

jerch hat geschrieben:Und zu guter Letzt gibts im Algorithmus auch dann noch Verbesserungsmöglichkeiten, ich sag nur mal Atkin

Allerdings ist der Performancegewinn von Atkin gegenüber dem Eratosthenes nicht mehr so groß (aber wenigstens deutlich messbar) - zumindest war das das Ergebnis meiner Experimente mit beiden Verfahren. Auf jeden Fall ist der Atkin-Algorithmus nicht von solch bestechender Schlichtheit wie der von Eratothenes ...

r00t hat geschrieben:Der einzige Nachteil ist jetzt eben,dass man nicht mehr sagen kann nur noch die Primzahlen zwischen 10 und 100 weil man ja die Primzahlen davor zum teilen braucht. Aber trotzdem vielen Dank für eure Hilfe!!!!

Hab dazu eine Idee. Du hast drei Variablen x, y,z. Mit x = 1 (sinniger Weise)
Das Intervall [y:z] ist der Bereich in dem gesucht werden soll.
Das Intervall [x(1):y] dient dazu alle Vielfachen der im Intervall enthaltenen Zahlen aus dem Intervall [y:z] zu streichen.

pyMarkus hat geschrieben:Hab dazu eine Idee. Du hast drei Variablen x, y,z. Mit x = 1 (sinniger Weise)
Das Intervall [y:z] ist der Bereich in dem gesucht werden soll.
Das Intervall [x(1):y] dient dazu alle Vielfachen der im Intervall enthaltenen Zahlen aus dem Intervall [y:z] zu streichen.

Auf die drei Fragezeichen kann ich so leider keine Antwort geben.
r00t meinte er könnte nicht mehr angeben aus welchem Intervall die Primzahlen stammen sollten, da die kleineren Zahlen, die nicht in dem Intervall liegen sonst nicht vorhanden sind. Deshalb werden alle Vielfachen der Zahlen von 1 bis Intervallbeginn aus dem Intervall in dem gesucht werden soll gestrichen.

langsam check i nemm so durch^^

Das deutsche Python-Forum

primzahlen errechnen

primzahlen errechnen

Re: primzahlen errechnen

Verbesserung

Re: Verbesserung

Re: Verbesserung

Re: Verbesserung