Primzahl-Check: Javascript > Delphi

[zecke]

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 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 (Ja Physik ist auch viel Mathe)



btw: Warum ist die 1 keine Primzahl?

[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
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..