Primzahlen
lima-city → Forum → Programmiersprachen → Delphi & Pascal
ausgabe
bedingung
bereich
code
fragesteller
funktion
index
kandidat
matrix
nutzen
obige notation
operation
primzahl
prozessor
rotz
teiler
test
testen
url
zahl
-
Hey, Ich brauche einen Denkanstoß: Wie bestimme ich, ob eine Zahl eine Primzahl ist :D?
Vielen Dank für eure Mühe schonmal ;)
Morph01 -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Dazu liefert Wikipedia ein recht gutes Ergebnis:
http://de.wikipedia.org/wiki/Primzahltest
Wähle einen entsprechenden Algorithmus, und implementiere ihn. Viel Spaß dabei
Hier findest du eine fertige, einfache Implementierung:
http://www.programmersheaven.com/mb/delphikylix/294826/294826/prime-numbers-help/ -
Du iterierst durch alle Zahlen, deren Quadrat kleiner ist als die zu prüfende Zahl. Am besten Anfangen mit 1 und in Zweierschritten, damit du die ganzen geraden Zahlen nicht machen musst. Dann siehst du ob die zu bestimmende Zahl modulo die Zahl, die gerade bei der Iteration entsteht, 0 ist. (Hoffe das war verständlich. Sonst nachfragen :))
Pseudocode:
while(i=3;i*i<Z;++i) { if(!Z%i) { return false; } } return true;
Beitrag zuletzt geändert: 21.10.2009 19:39:04 von nikic -
Also wäre es in etwa soetwas:
procedure TForm1.isprim(Zahl:integer):boolean var i,wurz:integer; begin wurz:=Trunc(sqrt(Zahl)); for i:=2 to wurz do begin if zahl/i0Trunc(Zahl/i) then resut := true; end; end; -
Wie groß sind denn die Zahlen, die du prüfen willst?
Und: mit welcher Sicherheit soll der Test eine Primzahl als solche erkennen und wie groß dürfen die Fehler erster und zweiter Art sein?
Hier ein paar Denkanstöße:
- Fermat-Test,
- Miller-Rabin-Test,
- Solovay-Strassen-Test,
- ECPP (mein Favorit).
Primzahlentests sind ja eines der großen Steckenpferde der Informatik und hier noch ein interessanter Fetzen aus Wiki:
Die den Primzahltest zugrundeliegende Problemstellung, festzustellen, ob eine Zahl prim ist, wird in der Informatik als PRIMES bezeichnet. Bis ins Jahr 2002 erhoffte man sich in der Komplexitätstheorie von ihr neue Erkenntnisse in Bezug auf das P-NP-Problem. Falls P≠NP gilt, muss nach dem Satz von Ladner ein Problem in NP\P existieren, welches nicht NP-vollständig ist[1]. PRIMES galt als ein potenzieller Kandidat für ein solches Problem.
Dies lag daran, dass PRIMES sowohl in der Komplexitätsklasse NP als auch in der Komplexitätsklasse co-NP liegt, und demnach nicht NP-vollständig sein konnte. Man kannte jedoch keinen nicht-probabilistischen Lösungsalgorithmus mit polynomieller Laufzeit. Daher war es fraglich, ob PRIMES auch in der Komplexitätsklasse P liegt.
2002 wurde jedoch von Agrawal, Kayal und Saxena mit dem AKS-Primzahltest ein solcher polynomieller Primzahltest gefunden. Damit war die lange Zeit offene Frage, ob PRIMES in P liegt, beantwortet. Dies brachte jedoch keine weitere Erkenntnis zum P-NP-Problem.
EDIT:
nikic schrieb: Du iterierst durch alle Zahlen, deren Quadrat kleiner ist als die zu prüfende Zahl. Am besten Anfangen mit 1 und in Zweierschritten, damit du die ganzen geraden Zahlen nicht machen musst. Dann siehst du ob die zu bestimmende Zahl modulo die Zahl, die gerade bei der Iteration entsteht, 0 ist. (Hoffe das war verständlich. Sonst nachfragen :))
morph01 schrieb: Also wäre es in etwa soetwas:
procedure TForm1.isprim(Zahl:integer):boolean var i,wurz:integer; begin wurz:=Trunc(sqrt(Zahl)); for i:=2 to wurz do begin if zahl/i0Trunc(Zahl/i) then resut := true; end; end;
Das Problem hier ist, dass das nur bis MAX_INT geht, also 2^64 wahrscheinlich, abhängig von der Architektur. Interessante und relevante Primzahlen, z.B. für Kryptoalgorithmen, sind leider ein bisserl größer.
Beitrag zuletzt geändert: 21.10.2009 19:40:00 von census -
Jaja klar, ich brauche etwas genaues, und Zahlen über 2^64 werde ich wohl nicht testen ;)
Und Primzahlen generieren - soll ich einfach in Zweierschritten hochzählen und mit meiner Prozedur jede einzelne Primzahl testen? Oder gibt es dafür andere Algorythmen? -
@census: Du glaubst nicht, das jemand, der hier im Forum danach fragt, Primzahlen in kryptografischer Höhe berechnen möchte... (das wusstest du aber auch ohne dass ich es dir sage)
@morph: Zumindest ist es das einfachste und das offensichtlichste. -
mhm... Aber die Performance (für meine Anwendung wichtig) ist wahrscheinlich relativ schlecht...
und wenn ich dann mal über die Integer-Grenzen stoße, werde ich mich an Census Beitrag erinnern und int64 oder so nehmen
(Welcher Variablentyp war nochmal nur Positiv? Cardinal oder so?)
Dankeschön für dei schnellen und vielen Antworten, ihr habt mir sehr geholfen ;)
morph01 -
morph01 schrieb:
mhm... Aber die Performance (für meine Anwendung wichtig) ist wahrscheinlich relativ schlecht...
und wenn ich dann mal über die Integer-Grenzen stoße, werde ich mich an Census Beitrag erinnern und int64 oder so nehmen
(Welcher Variablentyp war nochmal nur Positiv? Cardinal oder so?)
Dankeschön für dei schnellen und vielen Antworten, ihr habt mir sehr geholfen ;)
morph01
Auf heutigen Maschinen, kann die Performance um einen Integer auf Primalität zu testen gar nicht schlecht sein. Die empfohlene Brute-Force-Methode mit Ausprobieren jeder ungeraden Zahl bis zur Wurzel des Kandidaten hat den Aufwand O = n, ist also linear. Auf aktueller Hardware (und auch 4 Jahre alter Hardware) dürftest du da kaum die Laufzeit bemerken. -
Naja, 15 Sekunden rattert das Programm aber schon mit voller Rechenleistung wenn ich von 1-1000000 teste ;)
-
morph01 schrieb:
(Welcher Variablentyp war nochmal nur Positiv? Cardinal oder so?)
So ist es, hier eine Auflistung sämtlicher Datentypen:
http://www.epinasoft.com/delphikurs/dkk_datatypes.html -
ich hätte da eine Methode, dass Primzahlen bis 1000000 in einer Sekunde gerechnet wird... auf einem Pentium 1...
es gibt einen trick:du fängst bei 2 an... die beiden drunter kansnt du so hinschreiben, als anfangsbedingungen...
eine weitere Bedingung ist, dass zahlen nur bis x=n/2 geprüft werden... zahlen ab der hälfte des wertes brauchst du nicht mehr prüfen...
dann ermittelst du mithilfe dieser Primzahlen die nächste Primzahl durch rechnen mit den anderen Primzahlen. das wäre die 3.
Die schreibst du dann in eine Matrix. diese enthält {2, 3}.
So, jetzt läufst du das oben nochmal durch. Die 4. dann nimmt er die erste Zahl in der Matrix, also die 2, teilt die dadurch und weil rest 0 ist, bricht er die schleife ab und fährt mit
der 5 fort. die 5 teilt er durch die erste zahl in der Matrix, also die 2. so, rest bleibt... also würde er jettzt die nächste Zahl nehmen... aber da die 3 größer als 5/2 ist, bricht er ab und erklärt die 5 gleich als primzahl...
so, bei der 6 passiert dasselbe, wie bei der 4
bei der 7 würde er die 3 als letztes prüfen, da sie kleiner als 7/2 ist, aber die 5 würde er auslassen und sofort die 7 als Primzahl definieren.
und das würde immer so weiter gehen.
Ich schreib dir das mal als pseudocode hin, falls du es in Delphi nciht realisieren kannst, helf ich dir da gerne weiter...
int xMax=1000000; # kannst du auch über eine funktion übergeben... oder als zeiger... der wert wird nciht geändert int PrimMatrix[abs(xMax/2)+1]; # abs ist eine Funktion die den absoluten wert angibt, alsso die nachkommastellen abschneidet PrimMatrix[0]=2; int zaehler=3; #->diese Variable soll bis zum letzten Wert hochzählen, der auf Primzahl geprüft wird int aktPrim=0; #->diese Variable soll den Index der Matrize hochzählen, in 1er Schritten(index in matrix) int lastPrim=0; #dieser wert zählt den index der letzten bekannten Primzahl for(zaehler;zaehler<=xMax;zaehler++) { for (aktPrim;aktPrim<=lastPrim;aktPrim++) { if(aktPrim == lastPrim) { lastPrim++; PrimMatrix[lastPrim]=zaehler; } if(zaehler%PrimMatrix[aktPrim] == 0) { break; } } } # so und die Ausgabe kannst du machen wie bisher... du kansnt es in eine tabelle hauen... um das ganze sauber zu machen, sollteast du die komplette matrix in eine neue Matrix schreiben, die so groß ist, wie --->lastPrim+1<--- und dann darstellen , wie es dir beliebt...
so, wenn du das ungefähr so umsetzt, dann kannst du primzahlen bis ewig rechnen, ohne dass dein rechner außer Puste gerät... musst natürlich schauen, wie die Begrenzung für Matrizen ist... ander nennen den Datentyp Felder... ist aber mehr so ein Wessi-Begriff...
edit: hab kleine Verbesserung am Pseudocode vorgenommen
Beitrag zuletzt geändert: 22.10.2009 19:04:24 von sebulon -
sebulon schrieb:
eine weitere Bedingung ist, dass zahlen nur bis x=n/2 geprüft werden... zahlen ab der hälfte des wertes brauchst du nicht mehr prüfen...
ich bin zwar nicht der fragesteller, aber mich interressiert trotzdem, warum man das machen kann?? -
ganz einfach:
bei Primzahlen handelt es sich doch um zahlen, die nur durch 1 und sich selbst teilbar sind. und alle teiler sind ganzzahlen.
so, man kann eine Zahl in Primärfaktoren zerlegen. nehmen wir die 60. Die setzt sich zum beispiel aus folgenden Kombinationen zusammen:
2 - 30
3 - 20
4 - 15
5 - 12
6 - 10
so, da 2 immer der kleinstmögliche teiler ist, steht dem die größtmögliche Zahl gegenüber. in diesem Fall die 30
aber die würde nciht erreicht werden, da das programm bei 2 aufhört, weil keine primzahl vorhanden ist...
und so ist das immer... wenn was durch 2 teilbar ist, was bei 50% aller fälle ist, wird bei den Zahlen immer nur 1 Prüfung durchgeführt... und dann hat sich der Fall erledigt... lustig wird es im 5 stelligen bereich, wenn sich aus irgendeiner 4-stelligen primzahl was zusammensetzt oder aus 2 3-stelligen primzahlen...
-
t-li schrieb:
sebulon schrieb:
eine weitere Bedingung ist, dass zahlen nur bis x=n/2 geprüft werden... zahlen ab der hälfte des wertes brauchst du nicht mehr prüfen...
ich bin zwar nicht der fragesteller, aber mich interressiert trotzdem, warum man das machen kann??
Die Einschränkung ist richig und kann noch verstärkt werden, denn es reicht bis zur Quadratwurzel des Kandidaten zu testen und nicht bis zur Hälfte. Um die obige Notation zu Nutzen:
Genauer gesagt, die Kandidaten k(i) müssen aus der Menge K kommen um n > 3 auf Primalität zu testen:
Beitrag zuletzt geändert: 22.10.2009 20:08:53 von census -
census schrieb:
t-li schrieb:
sebulon schrieb:
eine weitere Bedingung ist, dass zahlen nur bis x=n/2 geprüft werden... zahlen ab der hälfte des wertes brauchst du nicht mehr prüfen...
ich bin zwar nicht der fragesteller, aber mich interressiert trotzdem, warum man das machen kann??
Die Einschränkung ist richig und kann noch verstärkt werden, denn es reicht bis zur Quadratwurzel des Kandidaten zu testen und nicht bis zur Hälfte. Um die obige Notation zu Nutzen:
Genauer gesagt, die Kandidaten k(i) müssen aus der Menge K kommen um n > 3 auf Primalität zu testen:
das ist auch richtig, aber die Umsetzung der sqwr - Wurzel-Funktion braucht auch enorm viel leistung... bis 500000 ist vielleicht meine lösung performanter, ab da bis 1000000 kann sich das wieder umkippen... müsste man sich mal die Funktion anschauen... -
sebulon schrieb: müsste man sich mal die Funktion anschauen...
FSQRT braucht auf einem Pentium 70 cycles.
SQRTPS braucht auf einem x86-64 39 cycles.
Ich hoffe ja mal, dass Pascal das ganze den Proz ausrechnen lässt und nicht zu Fuß per Hand tut. -
ja...
und eine Modulo-Operation? bei google findet man nur rotz...
aber die braucht doch niemals mehr als 20 cycles?
und die rechnung würde dann im unteren bereich zwar ein paar mal auftreten... aber im obereb bereich würden sich die ausführungen vermehren...
man muss ja auch beachten, dass diese ausführung bei JEDER zahl zum einsatz kommt, auch bei zahlen, wo bei der 2 bereits ausgeworfen wird... -
sebulon schrieb:
und eine Modulo-Operation? bei google findet man nur rotz...
Kein Prozessor (zumindest keiner, den ich kenne) kennt eine Modulooperation.
Alle, die ich kenne, haben eine Operation, die ein Register durch ein anderes teilt und das ganzzahlige Ergebnis in einem Zielregister speichert und den Rest (also den Modulo) in ein anderes.
Sprich für den Prozessor ist Modulo und Ganzzahldivision dasselbe, weil eine Operation beide Ergebnisse liefert.
EDIT: typo
Beitrag zuletzt geändert: 24.10.2009 1:08:28 von census -
@sebulon: Könntest du mir das ganze vielleicht in asm zusammenbasteln?
Nein:D Ich kann dem zwar nicht folgen, was du da gelabert hast, werde den pseudocode aber trotzdem einfach mal auf delphi portieren ;) Dankschön :) -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
