Primzahl-Check: Javascript > Delphi

[zecke]

mmm ich glaube ich bin zu blöd das richtig anzuwenden (nun mit functions habe ich noch nie was gebastelt ). 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

[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

Nein, Spaß! 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 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 von zecke:

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

Bei welchen Zahlen? Bei mir stimmen beide überein!
[Edit]Oh ok, bei Zahlen keiner 4
[Edit=2]Fehler gefunden!
Ersetze
Result:=not isnotPrime; durch
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.


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

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

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 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]

Danke - auch den Vorschlag werde ich mir anschauen.