Das Sieb des Eratosthenes auf dem JOYCE

Es gibt Projekte, die mich als Assembler-Programmierer neugierig machten, wie diese wohl zu implementieren sind. So waren das biher die Ackermann-Funktion und die Berechnung Osterns. Dann fand ich im Netz einen Artikel über das Sieb des Eratosthenes:
Aus [Wikipedia]:
Das Sieb des Eratosthenes ist ein Algorithmus zur Bestimmung einer Liste oder Tabelle aller Primzahlen kleiner oder gleich einer vorgegebenen Zahl. Er ist nach dem griechischen Mathematiker Eratosthenes von Kyrene benannt. Allerdings hat Eratosthenes, der im 3. Jahrhundert vor Christus lebte, das Verfahren nicht entdeckt, sondern nur die Bezeichnung „Sieb“ für das schon lange vor seiner Zeit bekannte Verfahren eingeführt.
Zunächst werden alle Zahlen 2, 3, 4,... bis zu einem frei wählbaren Maximalwert S aufgeschrieben. Die zunächst unmarkierten Zahlen sind potentielle Primzahlen. Die kleinste unmarkierte Zahl ist immer eine Primzahl. Nachdem eine Primzahl gefunden wurde, werden alle Vielfachen dieser Primzahl als zusammengesetzt markiert. Man bestimmt die nächstgrößere nicht markierte Zahl. Da sie kein Vielfaches von Zahlen kleiner als sie selbst ist (sonst wäre sie markiert worden), kann sie nur durch eins und sich selbst teilbar sein. Folglich muss es sich um eine Primzahl handeln. Diese wird dementsprechend als Primzahl ausgegeben. Man streicht wieder alle Vielfachen und führt das Verfahren fort, bis man am Ende der Liste angekommen ist. Im Verlauf des Verfahren werden alle Primzahlen ausgegeben.
Da mindestens ein Primfaktor einer zusammengesetzten Zahl immer kleiner gleich der Wurzel der Zahl sein muss, ist es ausreichend, nur die Vielfachen von Zahlen zu streichen, die kleiner oder gleich der Wurzel der Schranke S sind.
Ebenso genügt es beim Streichen der Vielfachen, mit dem Quadrat der Primzahl zu beginnen, da alle kleineren Vielfachen bereits markiert sind.
Das Verfahren beginnt also damit, die Vielfachen 4, 6, 8,... der kleinsten Primzahl 2 durchzustreichen. Die nächste unmarkierte Zahl ist die nächstgrößere Primzahl, die 3. Anschließend werden deren Vielfache 9, 12, 15,... durchgestrichen, und so weiter.

Implementierung


Eine beispielhafte Implementierung des Algorithmus als Pseudocode:
An diesem Algorithmus fällt die Funktion sqrt(N) auf, die ich gemäß des Artikels Tiny BASIC Square Root Routine umgesetzt habe. 
 const N = 10000
 var gestrichen: array [2..N] of boolean
 
 // Initialisierung des Primzahlfeldes
 // Alle Zahlen im Feld sind zu Beginn nicht gestrichen
 for i = 2 to N do
     gestrichen[i] = false
 end
 
 // Siebe mit allen (Prim-) Zahlen i, wobei i der kleinste Primfaktor einer zusammengesetzten
 // Zahl j = i*k ist. Der kleinste Primfaktor einer zusammengesetzten Zahl j kann nicht größer
 // als die Wurzel von j <= n sein.
 for i = 2 to sqrt(N) do
     if not gestrichen[i] then
         // i ist prim, gib i aus...
         print i; ", ";
         // ...und streiche seine Vielfachen, beginnend mit i*i
         // (denn k*i mit k<i wurde schon als Vielfaches von k gestrichen)
         for j = i*i to N step i do
             gestrichen[j] = true
         end
     end if
 end
 // Gib die Primzahlen größer als Wurzel(n) aus - also die, die noch nicht gestrichen wurden   
 for i = sqrt(N)+1 to N do
     if not gestrichen[i] then
         // i ist prim, gib i aus
         print i; ", ";
     end if
 end
Das Ergebnis sind die Quelldateien SIEB1 und SQRT.
Später fand ich einen Algorithmus, der ohne die Wurzelberechnung auskommt — sogar ohne Division, was die Programmierung erheblich erleichtert: 

Eratosthenes(n) {
  a[1] := 0                          
  for i := 2 to n do a[i] := 1
  p := 2
  while p²  ≤  n do {
    j := p²
    while (j  ≤  n) do {             
      a[j] := 0
      j := j+p
    }
    repeat p := p+1 until a[p] = 1   
  }
  return(a)
}
Das Ergebnis ist die Quelldatei SIEB2. hier mit der optionalen Eingabe des Maximalwertes.