Hat vielleciht jemand einen Vorschlag für einene verfahren, Primzahlen zu ermitteln?
Jede Zahl Modulo jeder Zahl unter ihr ist doch ziemlch langsam, auch wenn man vorher ersat mal mit modulo 2 und 5 vorsortiert.
Kennt jemand einen Algorythmus oderein verfahren, Primzahlenschnellerzu finden?
Grüße, Ryo
gelöscht_95543 RyoOhki „Wie crunche ich am schnellsten Primzahlen?“
Um ganz sicher gehen zu können, ob eine Zahl prim ist, muß man alle Zahlen in einer Schleife durchlaufen. In der Praxis ist das aber nicht möglich. Deshalb gibt es Tests, mit denen man mit beliebiger Wahrscheinlichkeit sagen kann, ob eine Zahl prim ist. z.B. kann man vorher bestimmen, daß die Zahl, von der man das wissen will, zu 99.99% prim sein soll. Es gibt verschiedene Tests dafür. Hier ist ein Beispiel und eine Erklärung zu dem Algorithmus zu finden:
http://rhlx01.rz.fht-esslingen.de/projects/krypto/prim/prim-3.html
thomas woelfer RyoOhki „Wie crunche ich am schnellsten Primzahlen?“
sieve of eratosthenes.
WM_FYI
Plazebo RyoOhki „Wie crunche ich am schnellsten Primzahlen?“
Sieb des Eratosthenes ist ziemlich fix, aber nicht die beste Methode glaube ich. Jede Zahl einzeln kannste in die Tonne treten.
Du machst dir am besten ein boolsches Array (geringer Speicherverbrauch und ist schnell).
Dann fängst du bei 2 an bis zu der Zahl die du ermittelt haben möchtest.
2 ist keine Primzahl, jedes ist immer das Vielfache von 2 eine Primzahl. Daher streichst du alles Vielfache von 2 (4, 6, 8, 10 etc.) indem du meinetwegen in die Stelle des Arrays auf True oder False setzt.
Dann gehst du wieder unüberprüft mit 3, also erhöhst immer um einen.
3 ist auch keine Primzahl und du setzt wieder in jede 6., 9. 12. Stelle usw. das Array auf True oder False (das kannst du nach Belieben machen).
Wenn du es später anzeigen willst nimmst du einfach alle Zahlen aus dem Array raus, welche du mit True oder Boolean als Primzahlen markiert hast.
Wenn du willst kann ich dir ein Delphi-Projekt dazu schicken. Aber ich vermute dass es noch bessere und schnellere Verfahren dazu gibt.
RyoOhki Plazebo „Sieb des Eratosthenes ist ziemlich fix, aber nicht die beste Methode glaube ich....“
Eratosthenes ist mir schon klar, die idee war mir auch gekommen.
Das Problem ist, dass ich eigentlich keine 'Zielprimzahl' habe, und das sieb-verfahren relatiev langsam wird wenn man große arrays nimmt.
Trotzdem vielen Dank!
Grüße, Ryo
Plazebo RyoOhki „Eratosthenes ist mir schon klar, die idee war mir auch gekommen. Das Problem...“
Es gibt auch dynamische Arrays. Jedoch ist der Speicherverbrauch relativ hoch wenn die dynamisch sind, ich weiß auch nicht ob sie vielleicht langsamer sind.
mr.escape Plazebo „Sieb des Eratosthenes ist ziemlich fix, aber nicht die beste Methode glaube ich....“
>2 ist keine Primzahl ... Nicht? Dachte immer, zwei wäre die kleinste primzahl. Tja, so kann man sich irren.
>Daher streichst du alles Vielfache von 2 (4, 6, 8, 10 etc.) indem du meinetwegen in die Stelle des Arrays auf True oder False setzt.
Dann gehst du wieder unüberprüft mit 3, also erhöhst immer um einen.
3 ist auch keine Primzahl und du setzt wieder in jede 6., 9. 12. Stelle usw. das Array auf True oder False (das kannst du nach Belieben machen).
Nach der zwei (sofern man das array nicht sogar nur für ungerade zahlen anlegt, das spart auch speicherplatz) überprüft man nur noch die (ungeradzahligen) vielfachen von ungeraden, denn die sind mit der zwei ja schon aus dem rennen, d.h. man erhöht immer um zwei, ausgehend von 3 (3,5,7,9, etc.).Zusätzlich lässt man alle weg, die schon in der tabelle gekillt sind (z.b. 9, 15, 21, etc.), dann geht es etwas schneller.
mr.escape
RyoOhki mr.escape „ 2 ist keine Primzahl ... Nicht? Dachte immer, zwei wäre die kleinste primzahl....“
Wie schon gesagt, das Problem ist hierbei, das man einen maximalen Oberwert vorgeben muss, bis zu dem man prüfen kann.
Grüße, Ryo
Kolti Plazebo „Sieb des Eratosthenes ist ziemlich fix, aber nicht die beste Methode glaube ich....“
Warum sollte 2 keine Primzahl sein?
Dr. Hook Kolti „2 ist keine Primzahl?“
Hi Kolti,
Du hast vollkommen recht! Die 2 ist sehr wohl eine Primzahl! Da hat Plazebo mal wieder daneben gehauen. Weiter unten setzt er noch einen drauf, und behauptet, daß die 3 ebenfalls keine Primzahl wäre. Nochmal daneben!! Dabei ist die Definition so einfach. Eine Zahl ist dann eine Primzahl, wenn sie nur durch 1 oder sich selbst geteilt werden kann um als Teilungsergebnis eine natürliche Zahl zu erhalten. Also keine Kommazahlen oder so.
Die 2 ist übrigens die einzige gerade Primzahl die es gibt. (Logisch!)
cu
Dr. Hook
PS: Schade, daß unser Chefmathematiker (Xafford) das nicht gelesen hat.
Plazebo RyoOhki „Wie crunche ich am schnellsten Primzahlen?“
ähm, sorry wegen den Fehlern, ich hoffe du verstehst das trotzdem. Die Beschreibung gehört zu dem Sieb des Erathostenes.
Evonaut RyoOhki „Wie crunche ich am schnellsten Primzahlen?“
Hört sich nach O(n²) an. Könnte unter umständen schneller gehen.
Bruder*chorge RyoOhki „Wie crunche ich am schnellsten Primzahlen?“
Hy
Ich habe gelesen, das man für Primzahlen ab 10 000 000 Stellen
150 000 $ und aufwärts bekommt ! Ist vielleicht ein kleiner Ansporn
für euch !
MfG
RyoOhki Bruder*chorge „Hy Ich habe gelesen, das man für Primzahlen ab 10 000 000 Stellen 150 000 und...“
10000000000 Stellen? Das ist ne Menge wür dich sagen ;-)!
So eine Lange Zahl auf ihre teilbarkeit hin zu prüfen würde ja schon ewig dauern, aber da ich nicht weis, in was für variabeln ich sowas speichern soll würde ic hsagen, dass man die zu testende Zahl stelenweise in ein Array und die Zahl mit der man dividieren will stellenweise in ein Array einfügen und dann anschließend die einzelnen Stellen dividieren muss. Also wie bei der schriftlichen Division. das wären dann nochmal zig Teilschritte. außerdem währe ein solche array dann 1- bis 20000000 Byte groß, also die zahl 10 bis 20 Megabyte wenn man ein Char oder Short-Array verwenden würde. Oder irre ich mich? Wie geht man mit so großen Zahlen um?
Grüße, Ryo
Doubleight RyoOhki „Wie crunche ich am schnellsten Primzahlen?“
Da man jede Zahl in ihre Primfaktoren zerlegen kann, muß man lediglich durch die Primfaktoren teilen, um zu sehen ob es eine Primzahl ist oder nicht. Man beginnt mit der 2, die speichert man in dem Array ab. Jetzt macht man eine Schleife und prüft ob sich die Zahl durch eine der Zahlen in dem Array (sind nur Primzahlen drinnen) teilen läßt, wenn nicht haben wir eine neue Primzahl gefunden und schreiben diese in das Array. Damit kann man dann alle Zahlen bis zu einer gewünschten Obergrenze prüfen.
Ach ja, der Herr Evonaut kann anscheinend nur schlau daher reden, schau mal ob du es in O(logn) schaffst.
RyoOhki Doubleight „Da man jede Zahl in ihre Primfaktoren zerlegen kann, muß man lediglich durch...“
d.h. ich mus slediglich versuchen, eine zahl durch alle vorrangegangenen primzahlen zu teilen, nicht durch JEDE vorrangegangene Zahl *rechne*
Grüße, Ryo
Kolti RyoOhki „Wie crunche ich am schnellsten Primzahlen?“
Geh doch mal in eine Suchmaschine und gib Primzahl ein.
RyoOhki Kolti „Geh doch mal in eine Suchmaschine und gib Primzahl ein.“
Ja, die Idee hatte ich auch schon ;-)
aber weil mein eigener firmenrechner keinen internetanschluss hat und ich dann immer nur mal kurz an dem vom Kollegen rankann, habe ich leider nicht die Zeit, selber zu suchen ...
Nur die Antworten zu lesen ist schnell erledigt.
Grüße, Ryo
