Primzahl-Check: Javascript > Delphi

[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