Ein Primzahlen-Test nach Eratosthenes in JavaScript.
Erfolgreich getestet mit Internet Explorer 5.5 und 6.0, Netscape Navigator 4.75, 6.01 - 6.21, 7.0 und 7.1, Mozilla 1.0, 1.21 und 1.4 sowie mit Opera 5.11, 6.0, 6.01 und 7.01.
Demo:
Ab etwa 10.000.000.000 nimmt die Rechenzeit spürbar zu.
Die größte Primzahl, die mir das Script bisher berechnen konnte ist: 199.999.999.999.997
(Jedoch erst nach 46 Minuten Wartezeit und dem Wegklicken dreier Warnmeldungen meines Browsers.
Deutlich schneller dagegen (~ 2 min), ist dieser Test als Java-Applet.)
Einige weitere Testergebnisse zur Einschätzung der ungefähren Rechendauer (900 MHz, IE 5.5):
Die theoretisch größte mit diesem Script berechenbare Primzahl ist 4.503.599.627.370.449 = 2^52-47.
Der Quellcode:
<html>
<head>
<title>Primzahlen-Test mit JavaScript</title>
<script language="JavaScript">
var i, j, n, nPrime, xPrime, p=new Array(), x;
p[0] = 2;
function init() {
x = document.primeform.primeinput.value;
if(x>4503599627370496)
alert("Zahl ist zu groß ! \nMaximum: \n4.503.599.627.370.496");
else if(x<2 || x%1!=0) alert(x+" ist keine Primzahl !");
else if(x%2==0 && x!=2) alert(x+" =\n"+2+" * "+x/2);
else isPrime(x);
}
function isPrime(x) {
xPrime=true, j=0, n=3;
while(n*n<=x) {
i=0, nPrime=true;
while(p[i]*p[i]<=n) {
if(n%p[i]==0) {
nPrime = false;
break;
}
i++;
}
if(nPrime) {
if(x%n==0) {
alert(x+" =\n"+n+" * "+x/n);
xPrime = false;
break;
}
p[j]=n;
j++;
}
n+=2;
}
if(xPrime) alert(x+"\nist eine Primzahl !");
}
</script>
</head>
<body onload="document.primeform.primeinput.focus()">
<form name="primeform" action="javascript:init()">
<p>
<input name="primeinput">
<input type="button" value="Prüfen" onclick="init()">
</p>
</form>
</body>
</html>
Ausführlichere Informationen zu diesem Test-Verfahren finden Sie in der Applet-Rubrik unter 'Eratosthenes-Sieb'.
(Überings: Wenn Sie ein WAP- und WMLScript-fähiges Handy besitzen, können Sie den Primzahlen-Test in einer WMLScript-Version auch unterwegs nutzen: www.wmlscript.de/wap.)