primzahlen errechnen

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
r00t
User
Beiträge: 7
Registriert: Samstag 18. April 2009, 12:58

primzahlen errechnen

Beitragvon r00t » Samstag 18. April 2009, 13:03

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]
jerch
User
Beiträge: 1622
Registriert: Mittwoch 4. März 2009, 14:19

Beitragvon jerch » Samstag 18. April 2009, 14:56

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.
Zuletzt geändert von jerch am Samstag 18. April 2009, 15:01, insgesamt 1-mal geändert.
Benutzeravatar
Blade Runner
User
Beiträge: 21
Registriert: Montag 23. Februar 2009, 11:41

Re: primzahlen errechnen

Beitragvon Blade Runner » Samstag 18. April 2009, 15:00

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))
Roy Batty hat geschrieben:All those moments will be lost in time, like tears in rain ... time to die.
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Beitragvon str1442 » Samstag 18. April 2009, 16:20

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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Samstag 18. April 2009, 16:48

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.
r00t
User
Beiträge: 7
Registriert: Samstag 18. April 2009, 12:58

Verbesserung

Beitragvon r00t » Sonntag 19. April 2009, 13:01

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!!!!
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Re: Verbesserung

Beitragvon numerix » Sonntag 19. April 2009, 14:24

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.
jerch
User
Beiträge: 1622
Registriert: Mittwoch 4. März 2009, 14:19

Beitragvon jerch » Sonntag 19. April 2009, 16:46

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 :shock:

Viel Spaß beim Tüfteln, Jerch
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Sonntag 19. April 2009, 17:48

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 ... :)
pyMarkus
User
Beiträge: 9
Registriert: Montag 20. April 2009, 19:05
Kontaktdaten:

Re: Verbesserung

Beitragvon pyMarkus » Montag 20. April 2009, 19:26

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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Re: Verbesserung

Beitragvon numerix » Montag 20. April 2009, 19:29

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.



:?: :?: :?:
pyMarkus
User
Beiträge: 9
Registriert: Montag 20. April 2009, 19:05
Kontaktdaten:

Beitragvon pyMarkus » Montag 20. April 2009, 19:40

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.
r00t
User
Beiträge: 7
Registriert: Samstag 18. April 2009, 12:58

Beitragvon r00t » Montag 20. April 2009, 20:42

langsam check i nemm so durch^^

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder