Sieb von Atkin

Das Sieb von Atkin ist ein modernes und schnelles Verfahren (Algorithmus) zur Bestimmung von Primzahlen. Es beruht auf dem wohl bekanntesten Verfahren zur Primzahlbestimmung – dem Sieb des Eratosthenes. Auf dieser Seite könnt ihr euch ansehen, wie das Verfahren funktioniert. Diese Implementierung berechnet euch Primzahlen bis zu einer Obergrenze von 1 Million. Außerdem könnt ihr euch den hier eingesetzen (Javascript-) Code ansehen oder downloaden.

Sieb von Atkin

Das Sieb von Atkin ist eine optimierte Version des Sieb des Eratosthenes und wurde von A. O. L. Atkin und Daniel J. Bernstein entwickelt. Seine genaue Wirkungsweise wird auf Wikipedia beschrieben. Außerdem findet man dort den Pseudocode, welcher sich leicht umsetzen lässt (vgl. dazu den hier abgedruckten Javascript-Code).

Algorithmus testen und Primzahlen berechnen lassen

Bestimme alle Primzahlen ≤


Sieb von Atkin – Code zum Demonstrationsbeispiel auf dieser Seite

Der unten dargestellte Code ist eine voll funktionstüchtige HTML-Seite und arbeitet genau wie das Formular mitsamt Code auf dieser Seite. Es steht natürlich auch als ZIP-Datei zum download bereit.

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Sieb von Atkin - Demonstration</title>
<script type="text/javascript">
function runSiebVonAtkin(myForm)
{
	limit = Number( myForm.limit.value ); 
	sqrtlimit = Math.sqrt(limit);
	
	is_prime = new Array();
	for (i = 5; i <= limit; i++) { 
		is_prime[i] = false; 
	} 
	
	for (x=1; x <= sqrtlimit; x++) { 
	
		xsqr = x*x;
		
		for (y=1; y <= sqrtlimit; y++) { 
            
			ysqr = y*y;
			
			n = 4 * xsqr + ysqr; 
			nmod12 = n%12;
			if (n <= limit &#038;&#038;  (nmod12 == 1 || nmod12 == 5)) { 
				is_prime[n]=(is_prime[n])?false:true;
			} 
 
			n = 3 * xsqr + ysqr; 
			if (n <= limit &#038;&#038;  n%12 == 7) { 
				is_prime[n]=(is_prime[n])?false:true;
			} 
 
			n = 3 * xsqr - ysqr; 
			if (x > y &#038;&  n <= limit &#038;&#038; n%12 == 11) { 
				is_prime[n]=(is_prime[n])?false:true;
			} 
		} 
	}
 
	for (n = 5; n <= sqrtlimit; n++) { 
		if (is_prime[n]) { 
			grenze = Math.floor(limit/n/n);
			nsqr = n*n;
			for (k=1; k <= grenze; k++) { 
				is_prime[k * nsqr] = false; 
			} 
		} 
	} 
	
	counter = 2;
	out = '2\t3\t';
	for (n = 5; n <= limit; n++) { 
		if (is_prime[n]) { 
			counter++;
			if (counter%10==0)
				out += n + '\n';
			else
				out += n + '\t';
		} 
	}
	myForm.erg.value = out;
}
</script>
</head>

<body>
<form>
  Primzahlen &le; <input name="limit" type="text" value="1500" size=3 />
  <input type="button" value="Starte Sieb von Atkin" 
         onClick="runSiebVonAtkin(this.form);" /> 
  <input type="reset" value="Reset" /><br />
  <textarea name="erg" cols="80" rows="27"></textarea>
</form>
</body>
</html>

Auch interessant: