MODULE Prim2;

FROM InOut IMPORT WriteInt;

CONST n = 1000;

VAR i,k: INTEGER;
(* k: min = 2, max = 31 *)
(* i: min = 2, max = 1000 *)
    prim: BOOLEAN;
(* prim: min = 0, max = 1 *)

PROCEDURE Sqrt(a: INTEGER): INTEGER;
(* a: min = 2, max = 1000 *)
(* Der schnellste, mir bekannte Wurzel-Algorithmus.
   Er prüft, in welchem Zahlenbereich a ist und nimmt davon ausgehend die
   erste Näherung. Die Steigung der Wurzelfunktion in den verschiedenen
   Bereichen wird als konstant angesehen. Das Ergebnis wird um 1 vermindert,
   wenn es größer als sqr(a) ist, damit es mit trunc(sqrt(a)) übereinstimmt *)

VAR b: INTEGER;
(* b: min = 1, max = 31 *)

BEGIN
 (* 999 Aufrufe *)
  IF    a<8H    THEN b := a DIV   4H +  1H;
  ELSIF a<20H   THEN b := a DIV   8H +  2H;
  ELSIF a<80H   THEN b := a DIV  19H +  4H;
  ELSIF a<200H  THEN b := a DIV  20H +  8H;
  ELSIF a<800H  THEN b := a DIV  40H + 10H;
  ELSIF a<2000H THEN b := a DIV  80H + 20H;
  ELSIF a<8000H THEN b := a DIV 100H + 40H;
  ELSE               b := a DIV 200H + 80H END;
  b := (b + a DIV b) DIV 2; IF b*b>a THEN DEC(b) END;
  RETURN b;
END Sqrt;

BEGIN
  FOR i:=2 TO n DO
 (* 999 Durchläufe *)
    prim := TRUE;
    FOR k:=2 TO Sqrt(i) DO
 (* 19615 Durchläufe *)
      IF i MOD k = 0 THEN prim := FALSE END;
    END;
    IF prim THEN WriteInt(i,4) END;
  END;
END Prim2.