Thema Datum  Von Nutzer Rating
Antwort
10.04.2008 17:00:04 Anfänger
NotSolved
Blau Aw:Primzahlen?? Hilfe!!
 10.04.2008 21:44:23 Martin O.
NotSolved
12.04.2008 19:12:18 SirLeon
NotSolved

Ansicht des Beitrags:
Von:
Martin O.		 Datum:
10.04.2008 21:44:23		 Views:
941		 Rating:
     
Antwort:
  Ja
Thema:
Aw:Primzahlen?? Hilfe!!
Hallo!

Deine Funktion ist bis auf einen kleinen Fehler perfekt, denn 2 ist per Definition eine Primzahl. Zur Zeit gibst du für 2 noch False zurück.

Jetzt zu Optimierungsmöglichkeiten:
Deine Schleife startet bei 3 und geht dann alle Zahlen bis (zahl - 1) durch. Da sind auch alle geraden Zahlen dazwischen dabei. Das ist unnötig, denn du hast ja schon geprüft, ob die Zahl durch 2 teilbar ist. Weitere Gerade zahlen zu prüfen bringt keinen Gewinn mehr.
Die For-Schleife läßt sich also so verbessern:

For i = 3 To zahl - 1 Step 2

Jetzt werden nur noch ungerade Zahlen zwischen den beiden Grenzen ausprobiert, was die Anzahl der Versuche schon halbiert.

Einen zweiten Trick gibt es noch für das Ende der Suche, und zwar genügt es bis zur Quadratwurzel aus der zu prüfenden Zahl zu suchen. Wenn die Quadratwurzel keine ganze Zahl ergibt, dann kannst du abrunden.
Die For-Schleife sieht dann so aus:

For i = 3 To Int(Sqr(zahl)) Step 2

Angenommen, man möchte die Zahl 200 prüfen. Die Quadratworzel ist 14,14... oder abgerundet 14. Wenn man die Division durch 14 überprüft hat, dann ist es nicht mehr nötig die Zahlen 14*2, 14*3, 14*4, ..., 14*14 zu prüfen. Das gleich gilt auch für 13*2, ..., 13*13, für 12*2, ..., 12*12. Aufrunden braucht man deshalb nicht, weil 15*15 schon größer als 200 ist - 15 kann also kein Teiler von 200 sein.

Das Verfahren heißt Probedivision - mehr dazu findest du unter http://de.wikipedia.org/wiki/Probedivision.

Falls du noch mehr optimieren möchtest, müssen die Mathematiker ran. Mehr dazu findest du unter http://de.wikipedia.org/wiki/Primzahltest.

Schöne Grüße!
Martin

Ihre Antwort
  • Bitte beschreiben Sie Ihr Problem möglichst ausführlich. (Wichtige Info z.B.: Office Version, Betriebssystem, Wo genau kommen Sie nicht weiter)
  • Bitte helfen Sie ebenfalls wenn Ihnen geholfen werden konnte und markieren Sie Ihre Anfrage als erledigt (Klick auf Häckchen)
  • Bei Crossposting, entsprechende Links auf andere Forenbeiträge beifügen / nachtragen
  • Codeschnipsel am besten über den Code-Button im Text-Editor einfügen
  • Die Angabe der Emailadresse ist freiwillig und wird nur verwendet, um Sie bei Antworten auf Ihren Beitrag zu benachrichtigen
Thema: Name: Email:



  • Bitte beschreiben Sie Ihr Problem möglichst ausführlich. (Wichtige Info z.B.: Office Version, Betriebssystem, Wo genau kommen Sie nicht weiter)
  • Bitte helfen Sie ebenfalls wenn Ihnen geholfen werden konnte und markieren Sie Ihre Anfrage als erledigt (Klick auf Häckchen)
  • Bei Crossposting, entsprechende Links auf andere Forenbeiträge beifügen / nachtragen
  • Codeschnipsel am besten über den Code-Button im Text-Editor einfügen
  • Die Angabe der Emailadresse ist freiwillig und wird nur verwendet, um Sie bei Antworten auf Ihren Beitrag zu benachrichtigen

Thema Datum  Von Nutzer Rating
Antwort
10.04.2008 17:00:04 Anfänger
NotSolved
Blau Aw:Primzahlen?? Hilfe!!
 10.04.2008 21:44:23 Martin O.
NotSolved
12.04.2008 19:12:18 SirLeon
NotSolved