Primzahl-Check: Javascript > Delphi

[zecke]

:hi:

ich bin auf einen Primzahlcheck gestossen, der erstaunlich schnell überprüft ob eine eingegebene Zahl eine primzahl ist. Gefunden auf Javarea.de. Da ich Java soviel zu tun habe, wie mit dem Bau eines Seekreuzers, frage ich euch, ob mir jemand erläutern kann, welche Rechenoperationen durchgeführt werden. Manches kann ich mir selbst erklären, aber auch nicht mit Sicherheit.

Würde mich freuen über eine Antwort.

Hier der JavaScript-Code:

Code:

<SCRIPT LANGUAGE="JavaScript">
<!--
function calculate(form) {
var num=parseInt(form.number.value);
if (isNaN(num) || num < 0) {
form.result.value=(form.number.value + " ist keine gültige Zahl! ");
}
if (num == 1) {
form.result.value=("1 ist eine Primzahl!");
}
for (var i=2;i<num;i++) {
if (num % i == 0) {
var prime="yes";
form.result.value=(num + " ist keine Primzahl. Sie ist teilbar durch " + i );
break;
}
if (num % i != 0) var prime="no";
}
if (prime == "no") form.result.value=(num + " ist eine Primzahl!");
}
// -->
</SCRIPT>

[BenjaminH]

Code:

for (var i=2;i<num;i++) {
if (num % i == 0) {
var prime="yes";
form.result.value=(num + " ist keine Primzahl. Sie ist teilbar durch " + i );
break;
}
if (num % i != 0) var prime="no";
}
if (prime == "no") form.result.value=(num + " ist eine Primzahl!");
}

Das ist der interessante Teil, davor werden nur die Variablen initialisiert:

Delphi-Quellcode:

function IsPrime(p:Integer):Boolean;
Var i:Integer;
    isnotPrime:Boolean;
Begin
  If p>1 Then
  Begin
    for i:=2 to p do//p ist die zu testende Zahl, mir ist kein besserer Name eingefallen
  //ich glaube for i:=2 to p div 2 do müsste reichen
    Begin
      IsnotPrime:= (p mod i)=0;
      If IsnotPrime Then
        break;
    end;
    Result:=not IsnotPrime;
  end
  Else
    Result:=false;
end;

//Achja, die sagen 1 ist eine Primzahl, das ist natürlich falsch..
[Edit]Rückgabewert der Funktion eingetragen..
[Edit=2]Deklariation der Variable i vergessen...

[ste_ett]

- Prüfung, ob die Zahl 1 ist

wenn ja, wird sofort eine positive Rückmeldung rausgegeben

wenn nicht, durchläuft das Programm eine Schleife von 2 bis zu der Zahl (bis zur Wurzel der Zahl reicht vollkommen, da könnte man nochmal Zeit sparen) und bricht ab, wenn die Zahl durch eine Zahl ausser 1 und sich teilbar ist

ganz normales Verfahren :)

[BenjaminH]

Zitat:

Zitat von ste_ett

- Prüfung, ob die Zahl 1 ist

wenn ja, wird sofort eine positive Rückmeldung rausgegeben

Wenn dann eine negative...

[zecke]

Nun ob die eins eine Primzahl ist oder nicht, ist ansichtssache und leigt in der Betrachtung des "oder"'s welches die Primzahl an sich definiert. Ist es ein einschliessendes oder ein ausschliessendes (~entweder oder) "oder". Darüber ist man sich nicht im Klaren, manche sagen es ist eine Primzahl manche sagen es ist keine. Hängt eben vom "oder" ab.

Danke schon ein mal für die function. Werde sie nachher ausgiebig benutzen und bearbeiten.

[BenjaminH]

Eine Primzahl ist als eine Zahl mit genau 2 Teilern definiert... also ist die 1 keine!
Wenn die 1 Primzahl wäre, dann wäre die eindeutigkeit der Primfaktorzerlegung nicht mehr gegeben:
29=3*13=1*3*13=1^10*3*13

[zecke]

Ja, Du hast Recht. Mein (Ex-)Mathelehrer hat Mist erzählt... Der Typ ist unmöglich, er ist nicht nur ein schlechter Pädagoge (nahezu gar keiner) sondern auch nicht so gut in Mathe, erklärt warum er Physik und nicht Mathematik studiert hat :stupid: (Ja Physik ist auch viel Mathe)

:thumb:

btw: Warum ist die 1 keine Primzahl?

:cheers:

[negaH]

Für eine wirklich schnelle Primzahlüberprüfung < 2^32 solltest du dir mal diese http://dennishomepage.gugs-cats.dk/IsPrimeChallenge.htm Seite anschauen.

Gruß Hagen

[zecke]

Danke negaH für den Link, schaue ich mir auch mal an.

@ BenjaminH:

Im Moment habe ich nur mit deinem Code-Schnipsel Probleme. Ich verstehe die Ausgabe nicht ganz, also wo ich dem Rechner quasi sage, dass das Ergebnis prim ist oder nicht. Kannst Du mir da auf die Sprünge helfen, damit ich da eine Ergebnisausgabe hinbekomme?

[BenjaminH]

Sorry, ich hab oben bei der Funktion den Rückgabewert vergessen gehabt :oops:
Du musst einfach diese Funktion mit der Zahl, von der du wissen willst, ob sie Prim ist, als Parameter aufrufen:

Delphi-Quellcode:

b1,b2,b3:Boolean;
b1:=IsPrime(5);
b2:=IsPrime(1);
b3:=IsPrime(5680);

b1 wird danach True, b2 und b3 false sein...
[Edit]Wenn du des mit C&P machst, kopier dir doch nochmal die neueste Version von oben, ich hatte noch die deklariation von i vergessen...
[Edit] Isnotprime wurde auch nicht deklariert..

[zecke]

mmm ich glaube ich bin zu blöd das richtig anzuwenden (nun mit functions habe ich noch nie was gebastelt :roll:). Das Ergebnis ist bei mir immer false :/

Ich rufe soetwas zB so auf:

Delphi-Quellcode:

Edit1.Text:=IntToStr(zahl);
Ergebnis:=IsPrime(StrToInt(zahl));

...

If Ergebnis=true then
begin
Showmessage('Ja die socke ist grün oder prim!');
end
else begin
Showmessage('Nein die Socke ist rot bzw. nicht prim!');
end;
end;

Bitte nicht hauen :angel2: :?

[BenjaminH]

So, ich hab mal ein beispielprogramm mit einer zweiten funktion, die doppelt so schnell ist angehängt, daran wirst du vermutlich auch die Verwendung erkennen...
Grüße Benjamin

[zecke]

ich will ein Kind von dir (aufs Alter schau) - nun warten wir noch ein wenig :mrgreen:

Nein, Spaß! :thumb: sieht einfach aus und funktioniert tadellos, aber das Zeitmessen scheint überflüssig, geht immer schneller als 1ms, mit beiden Verfahren. Wenn ich noch größere zahlen nehme bin ich aus dem Integer-Bereich draußen ^^

Vielen Dank für deine Hilfe!

Edit: Test 2 liefert immer "keine Primzahl". Ich benutze Test 1.

[BenjaminH]

Zitat:

Zitat von zecke

das Zeitmessen scheint überflüssig, geht immer schneller als 1ms, mit beiden Verfahren.

Klar, mit nicht Primzahlen geht es immer schnell!
Hast du es mal mit großen Primzahlen getestet? Geht auch schnell, aber bei mir waren es dann doch mal(lau Maple die 100 000. Primzahl, 1299709) 40ms bei Funktion 1 und 20ms bei der 2.

Zitat:

Zitat von zecke

Edit: Test 2 liefert immer "keine Primzahl". Ich benutze Test 1.

Bei welchen Zahlen? Bei mir stimmen beide überein! :gruebel:
[Edit]Oh ok, bei Zahlen keiner 4 :-(
[Edit=2]Fehler gefunden! :hello:
Ersetze

Delphi-Quellcode:

Result:=not isnotPrime;

durch

Delphi-Quellcode:

Result:=(not isnotPrime) or (i>p div 2);

Dann ist die 2. Funktion eindeutig schneller! :!:

[zecke]

nun ich habe die 1. Funktion eingebaut, wenn es eine primzahl ist, hasse rescht, dauert es etwas länger, da ich die Zeitmessung ausgebaut habe, kann ich nur ungefähr sagen, dass die feststellung das 2.147.483.647 (halt ohne punkte) eine Primzahl ist, ca 20 sekunden gedauert, länger auf keinen fall. das reicht für meine zwecke.
:thumb:

edit: das ergebnis mit der zahl 1299709 erscheint bei mir ohne verzögerung.

[BenjaminH]

Also, ich meine die zweite funktion lohnt sich eindeutig(zumindest bei solchen Zahlen):

Code:

Nach Test eins ist 2147483647 eine Primzahl
Das herauszufinden dauerte 34780ms
Nach Test zwei ist 2147483647 eine Primzahl
Das herauszufinden dauerte 18026ms

[zecke]

Ja mag sein ^^ aber ich habe jetz die erste so schön eingebaut und wie soll ich sagen... nun ich gehöre zu den gemütlichen Menschen :mrgreen:

Ich änders mal in die zweite um :> - danke dir :thumb:

edit: hab sie eingebaut:

Zitat:

Nach Test eins ist 2147483647 eine Primzahl
Das herauszufinden dauerte 26562ms
Nach Test zwei ist 2147483647 eine Primzahl
Das herauszufinden dauerte 13875ms

beide zusammen dauert aber verdammt lange deswegen benutze ich nur die zweite.

[alzaimar]

Bei mir erscheint auch der Test mit 2147483647 ohne Verzögerung (also nach 0ms). Allerdings benutze ich ein anderes Verfahren:
Ich prüfe nicht alle Zahlen bis N / 2, sondern nur bis s=Sqrt(N). Denn eine Zahl N kann nur Primfaktoren haben, die <=s sind.
Dann kann man noch die Tatsache ausnutzen, das für alle Primzahlen P > 3 gilt: P modulo 6 = 1 oder 5.

Delphi-Quellcode:

Function IsPrime (aNumber : Int64) : Boolean;
(********************************************************************
 * Ist aNumber eine Primzahl? Benutzt die Tatsache, das für alle    *
 * Primzahlen p > 3 gilt : p mod 6 = 1 oder 5.                      *
 *                                                                  * 
 * Das hier ist nicht der schnellste Algorithmus, aber lustig isser * 
 ********************************************************************)
Var
  iTest, iStop : Int64;

Begin
  Result := False;
  If aNumber < 2 Then Exit;
  if aNumber in [2,3,5] Then Begin
    Result := True;
    Exit;
    End;

  If aNumber mod 6 in [0,2,3,4] Then Exit; // Not a prime

  If aNumber mod 2 = 0 Then Exit;
  If aNumber mod 3 = 0 Then Exit;
  If aNumber mod 5 = 0 Then Exit;
  iStop := Trunc (0.5 + Sqrt(1.0*aNumber));
  iTest := 7;
  While iTest < iStop do begin
    If aNumber mod iTest = 0 Then Exit;
    inc (iTest,2);
    If aNumber mod iTest = 0 Then Exit;
    inc (iTest,4);
    End;
 Result := True;
End;

Beispielperformance (AMD 64):

• Test von 4294967294000017 (is wohl eine Primzahl) dauerte 7985 ms

[alzaimar]

Zitat:

Zitat von alzaimar

Bei mir erscheint auch der Test mit 2147483647 ohne Verzögerung (also nach 0ms). Allerdings benutze ich ein anderes Verfahren:
Ich prüfe nicht alle Zahlen bis N / 2, sondern nur bis s=Sqrt(N). Denn eine Zahl N kann nur Primfaktoren haben, die <=s sind.
Dann kann man noch die Tatsache ausnutzen, das für alle Primzahlen P > 3 gilt: P modulo 6 = 1 oder 5.

Delphi-Quellcode:

Function IsPrime (aNumber : Int64) : Boolean;
(********************************************************************
 * Ist aNumber eine Primzahl? Benutzt die Tatsache, das für alle    *
 * Primzahlen p > 3 gilt : p mod 6 = 1 oder 5.                      *
 *                                                                  * 
 * Das hier ist nicht der schnellste Algorithmus, aber lustig isser * 
 ********************************************************************)
Var
  iTest, iStop : Int64;

Begin
  Result := False;
  If aNumber < 2 Then Exit;
  if aNumber in [2,3,5] Then Begin
    Result := True;
    Exit;
    End;

  If aNumber mod 6 in [0,2,3,4] Then Exit; // Not a prime

  If aNumber mod 2 = 0 Then Exit;
  If aNumber mod 3 = 0 Then Exit;
  If aNumber mod 5 = 0 Then Exit;
  iStop := Trunc (0.5 + Sqrt(1.0*aNumber));
  iTest := 7;
  While iTest < iStop do begin
    If aNumber mod iTest = 0 Then Exit;
    inc (iTest,2);
    If aNumber mod iTest = 0 Then Exit;
    inc (iTest,4);
    End;
 Result := True;
End;

Beispielperformance (AMD 64):

• Test von 4294967294000017 (is wohl eine Primzahl) dauerte 7985 ms

EDIT:
Ich würde aber trotzdem das 'Sieve of Atkins' in der Implementierung von negaH nehmen und einfach schauen, ob das entsprechende Bit gesetzt ist. Googel mal danach oder suche hier im Forum. Da gab es vor Kurzem einen lustigen Thread.

[zecke]

:hi: Danke - auch den Vorschlag werde ich mir anschauen.

[negaH]

@Zecke:

schau dir wirklich mal den Link den ich dir gegeben habe an. Der von euch verwendetet Algorithmus ist in seiner Komplexität viel zu schlecht. Es geht also viel schneller, besonders bei großen Zahlen wird das deutlich. Probiere doch mal $FFFFFFFB aus.

Gruß Hagen

[alzaimar]

Zitat:

Zitat von negaH

@Zecke:
schau dir wirklich mal den Link den ich dir gegeben habe an. Der von euch verwendetet Algorithmus ist in seiner Komplexität viel zu schlecht.

Also, ich find' Dein ASM-Gewurschtle ehrlich gesagt, viel viel komplexer, aber Du meinst bestimmt 'Big Oh', bzw. den Zeitaufwand. Wenn ich bei 32 bit Zahlen gar nicht warten muss, reicht das doch. edit: Nicht das Du das missverstehst, dein Code ist wirklich marginal schneller: Nur etwas über 100 mal, das ist doch ... pah... ernüchternd :roteyes:

Welche Regeln verwendet denn der Algo? Das wäre imho interessant. Du scheinst da wirklich ein Experte zu sein. :thumb:

[negaH]

Der Algo. basierst auf einem SPP = Strong Pseudo Prime Test zu festen Basen. Auf http://primes.utm.edu/prove/prove2_3.html kannst du das nachlesen.

Zitat:

If n < 9,080,191 is a both 31 and 73-SPRP, then n is prime.
If n < 4,759,123,141 is a 2, 7 and 61-SPRP, then n is prime.

besonders diese Passage ist interessant da sie bei meinem Algorithmus angewendet wird.

Zusätzlich wird aber ein schnellerer Test vorgschaltet der den Kandidaten zu den ersten 32 Primzahlen bis 137 testet. Es ist also eine einfache Trial Division falls der Kandidat < 137 * 137 ist.

Bei beiden Tests werden extensiv modulare Divisionen benötigt. Die CPU Laufzeit der Divisionen ist aber wesentlich schlechter als die der Multiplikation. Ergo: wird der erste schnelle Test nicht per Divisionen durchgeführt sondern per Multiplikationen, man "dividiert modular" indem man mit dem modualeren Inversen der kleinen Primzahlen zu 2^32 den Kandidaten testet.

Eine ähnliche "Ersetzung" der langsammen Divisonen habe ich auch im nachfolgendem SPP Test angewendet. Statt aber mit dem modularem Inversen zu arbeitet arbeitet der SPP Test, bzw. genauergesagt dessen modulare Exponentation in der sogenannten Montgomery Domain. Montgomery war ein Mathematiker der verschiede Tricks entdeckt hat, ua. eben auch seinen am meist bekannten "Montgomer Trick". Mit diesem ist es möglich eben eine modulare Exponentation so umzubauen das statt der vielen modularen Divisionen nur Multiplikationen benötigt werden.

Die obige Unit ist dabei eine Weiterentwicklung meines ursprünglichen Sources, in einem Contest im FastCode Projekt. Mein ursprünglicher Source nutzte zb. eben nicht die Trialdivision zu den ersten 32 Primzahlen. Allereine schon dieser Test eliminiert eine sehr große Anzahl von zusammengesetzten Zahlen.

Bei beiden Tests lässt sich nun Assembler leider nicht vermeiden. D.h. eine reine PASCAL Imlpementation wäre eventuell zwar möglich würde aber einen enormen und unnötigen Overhead im erzeugten Compilat bedingen. Das ich also Assembler gewählt habe liegt im Grunde nur daran das nur damit bestimmte Operationen möglich waren. Zb. wird ein Überlauf bei mathem. Operationen durch die Auswertung der Prozessorflags als notwendiges Feature des Algorithmus durchgeführt. In reinem PASCAL hat man aber diese Möglichkeit nicht. Das der Code in Assembler ist liegt also nicht daran das er primär auf Performance entwicklet wurde, sondern nur daran das so die Möglichkeiten der CPU ausgenutzt werden konnten.

Zitat:

Du meinst bestimmt 'Big Oh'

Ja, eben die Komplexität des Verfahrens die als Big O angegeben wird.

Hagen schrieb:

Zitat:

Der von euch verwendetet Algorithmus ist in seiner Komplexität viel zu schlecht.

Gruß Hagen

[alzaimar]

Ich wollte schon den Fermat-Test vorschalten, aber scheiterte eben an diesem a^n mod (n-1)... Da hat Montogomery wohl einen Trick gefunden, sehe ich das richtig? Ich finde das wirklich sehr spannend und würde liebend gern meine Zeit mit solchen Geschichten verbringen, aber was mach ich? Projekte durchziehen, Beratung, etc... Man kann nicht Alles haben.

Auf jeden Fall danke für die Info.

Ach, O(Sqrt(N)) ist doch aber nicht zuuuu schlecht, oder? Der eine oder andere Algo wäre froh, wenn er so komplex wäre... :zwinker:

[negaH]

Erst die schlechte Nachricht, obiger Source ist ein Cut aus meiner Contributation zum FastCode Projekt, und wie üblich: er ist fehlerhaft. Anbei also die korregierte Version. Denn ich bon stutzig geworden als du schriebst das der Test "nur" 100 mal schneller als euer sein sollte. Er sollte nämlich bei weitem schenller laufen. Am besten mal alle ungeraden Zahlen von 1 bis 2^32-1 in einer Schleife durchlaufen lassen und die gemessene Zeit dann durch 2^31 teilen. Das ergibt dann den korrekten Zeitbedarf beider Verfahren.

Zitat:

Fermat-Test vorschalten, aber scheiterte eben an diesem a^n mod (n-1)...

Dieser Test ist veraltet und stellt die Basis des Rabin-Miller Verfahrens dar. Besser ist ein Strong Probable Pseudo Prime Test zu festen Basen.

Statt also a^n mod (n-1) wird folgenes benutzt:

N-1 = 2^s * d -> also s ist die Anzahl der trailing Null Bits in N. Man wird also N-1 solange rechts shiften wir das unterste Bit 0 ist. Dabei zählt man S in jedem Schritt +1 höher.

Nun folgt mit diesem zu ermitteltem d die modulare Exponentation bis

a^d == 1 mod n

oder

(a^d)^2^r == -1 mod n

ist, r wird dabei von 0 bis s iteriert. Die Kongruenz von == -1 mod N wird in positiven modularen Ringen vereinfacht dadurch das -1 mod N == (N -1) ist.

Gruß hagen

[negaH]

Zitat:

Da hat Montogomery wohl einen Trick gefunden, sehe ich das richtig?

Nicht für die Exponentation ansich. Im obigen Link zum Fastcode Projekt findest du verschiedene Verfahren. In meiner Unit wurde diese Exponentation einerseits mit normalen Division, also in der Normal Domain, und andererseits in der Montgomery Domain implementiert.

Man kann also die modulare Exponentation durchaus mit normalen Zahlen umsetzen und benötigt dazu nicht zwangsweise den Montgomery Trick. Der Trick ansich ändert nur die Zahlendarstellung auf eine Art & Weise das die wiederholt nötigen modularen Redukationen nach den modularen Multiplikationen eben nicht per Divisionen sondern mit Multiplkationen durchgeführt werden können. Da nun Multiplikationen auf Intel CPU's weitaus schneller sind ist diese Vorgehensweise sinnvoll.

Essentiell benutze ich zb. den Montgomery Trick in meiner Large Integer Library mit Integern bis zu 2^4096. Alles was darüber ist ist dann mit der schnellen Karatsuba Division nach Burnikel&Ziegler wieder wesentlich Performanter.

Mein erster Source den ich vor ca. 10 Jahren schrieb nutzt eben nicht die Montgomery Domain. Erst vor 2 Jahren, in der FastCode Competition, habe ich meinen IsPrime() Algo. auf Montgomery umgesetellt. Dies wurde sozusagen nötig da meine Competior meinen ursprüglichen Code durch Detailverbesserungen immer schneller machten. Eine weitere Beschleinigung des Verfahrens war also nur noch möglich indem ich neben dem Montgomery Trick die Trial Division ins Rennen warf und später diese Trial Division mit den modularen Inversen + Multiplikationen ausbaute :)

Sogesehen: der obige Source konnte nur entstehen weil sich verschiedene Leute in der FastCode Competition gegenseitig motivierten.

Gruß Hagen

[KLS]

Zitat:

Zitat von zecke

Ja mag sein ^^ aber ich habe jetz die erste so schön eingebaut und wie soll ich sagen... nun ich gehöre zu den gemütlichen Menschen :mrgreen:

Ich änders mal in die zweite um :> - danke dir :thumb:

edit: hab sie eingebaut:

Zitat:

Nach Test eins ist 2147483647 eine Primzahl
Das herauszufinden dauerte 26562ms
Nach Test zwei ist 2147483647 eine Primzahl
Das herauszufinden dauerte 13875ms

beide zusammen dauert aber verdammt lange deswegen benutze ich nur die zweite.

(mal aus dem urschleim hervorkram)

Also meine funktion (drei) topt das bei weitem...

Nach Test eins ist 2147483647 eine Primzahl
Das herauszufinden dauerte 22148.4769255396ms
Nach Test zwei ist 2147483647 eine Primzahl
Das herauszufinden dauerte 10020.2887859163ms
Nach Test drei ist 2147483647 eine Primzahl
Das herauszufinden dauerte 0.411961755996052ms

die funktion von hagen hab ich mir noch nicht angeschaut.

[alzaimar]

Zitat:

Zitat von KLS

Nach Test drei ist 2147483647 eine Primzahl
Das herauszufinden dauerte 0.411961755996052ms

die funktion von hagen hab ich mir noch nicht angeschaut.

Das würde ich aber mal tun, den Deine ist sogar langsamer als meine primitive Funktion ('IsPrime'). Vorausgesetzt, man ersetzt Int64 durch Cardinal.

[KLS]

wahnsinn.

Nach Test vier ist 2147483647 eine Primzahl
Das herauszufinden dauerte 0.00393678467571966ms

Da muss ich doch jetzt echt überlegen, was ich an meiner funktion noch optimieren könnte. aber so spontan fällt mir da nix ein.

[alzaimar]

Na, das Verfahren. Was sonst. Oder wie rechnest du das aus?

[KLS]

naja ich rechne einfach von 3 - wurzel n alles durch (bzw jede ungerade).

Code:

function IsPrime3(Zahl : Cardinal) : Boolean;
var
  i,grenze : Integer;
begin
  if zahl > 1 then
  Begin
    if Zahl mod 2 = 0 then
    begin
      result := zahl = 2;
      Exit;
    end;
    i := 3;
    grenze := Trunc(sqrt(Zahl));
    result := true;
    while (i <= grenze) and Result do
    begin
      Result := Zahl mod i <> 0;
      inc(i,2);
    end;
  end else result := false;
end;

[alzaimar]

Genau. Das ist ja schon mal etwas langsamer, als meine Version, die nur die Zahlen der Form 6n+/-1 prüft. Hagen verwendet jedoch einen völlig anderen Algorithmus.

Es gibt Prüfungen, die sehr sehr schnell erkennen, ob eine Zahl KEINE Primzahl ist. Wenn der Test fehlschlägt, heisst das noch nicht, das die Zahl eine Primzahl ist, aber immerhin. Dieser Test hat einen zweiten Parameter (A und B).

Wenn ich den Test für eine bestimmte Zahl zweimal durchführe, einmal mit A und einmal mit B, und der Test schlägt beidesmal fehl, dann ist die Zahl eine Primzahl! Das gilt dann für Zahlen bis zu einer bestimmten Größe. Für noch größere Zahlen kann man einen dritten Test zuschalten (mit einem weiteren Parameter C). Usw.

So ähnlich läuft es ab (kann mich in den Details aber irren).

[negaH]

Zitat:

So ähnlich läuft es ab (kann mich in den Details aber irren).

Du irrst nicht, wobei es denoch eine faszinierende Umschreibung ist :)

Einfacher gesagt: die Mathemtik die in den verschiednenen Algos. benutzt wird ist eine andere.

Die einfachste Methode ist eine Trial Division mit allen ungeraden Zahlen (und 2) von 2 beginnend bis Wurzel(N). Das Laufzeitverhalten ist das schlechteste aller verfahren und es wächst Quadratisch.

Ein leichte Abwandlung dieses Tests ist mit 6n+-1 zu arbeiten. Das reduziert die Komplexität nur um einen konstanten Faktor, verändert aber nicht deren Progression.

Eine noch bessere Abwandlung benutzt bei dieser Trialdivision nur Primzahlen bis Wurzel(N).

In meinen Algos. verwende ich eine ganz andere Sichtweise:

1.) des mathematiche Verfahren ist im Grunde nicht exakt. D.h. es kann nur 100% exakt erkennen ob eine Zahl X KEINE Primzahl ist, aber wenn es sagt es IST eine Primzahl dann muß dies leider nicht stimmen.

2.) Punkt 1.) wird aber irrelevant weil Andere Leute schon zumindestens alle Zahlen bis 2^32 mit diesem Verfahren überprüft haben und die Parameter für diesen Test verifiziert haben. D.h. mein Verfahren enthält schon unsichtbares Wissen und Informationen. Das wäre so als wenn man extern einmalig mit einem sehr langsammen Test eine tabelle aller Primzahlen erzeugen würde und dann in dere eigenen Anwndung nur noch diese Tabelle implementiert und die zu testende zahl darin nachschlägt.

3.) mein Test besteht im Grunde aus 2 einzelnen und ganz verschiedenen Tests. Als erstes wird eine Testdivision zu allen kleinen Primzahlen bis 137 druchgeführt, und erst danach als zweiter Test der SPP Test.

Wichtig ist aber im Resulat nur die Laufzeit des Verfahrens. Mein Test ist egal mit welcher zahl man arbeitet von der Komplexität her annähernd linear, ist also unabhängig vom Kandidaten den man testen möchte immer gleich schnell.

"Mein Test" ist aber eigentlich nicht von mir, sondern von Mathematikern. Das einzigste was ich geleistet habe ist das ich deren mathematische Grundlagen in ein effizientes Stück Source umgewandelt habe.

Gruß Hagen