Program Sieb_des_Eratosthenes;

{ written by MJ und JG }

Const max=10000;

{ Diese Version benutzt ein Array statt SET: }

Var sieb: ARRAY [1..max] OF BOOLEAN;
    i, j, a, b, m: INTEGER;

Procedure Ausgabe(Var f:text; a,b:integer);
  Const NpL = 10;     { Numbers per Line }
  Var i, count:integer;
  Begin
    count:=0;
    IF (a<=2) THEN    { Feld repräsentiert nur die ungeraden Zahlen }
    BEGIN
       Write(f, 2:6);
       count := 1;
    END;
    For i:=a to (b DIV 2) Do
      If sieb[i] Then
        Begin
          write(f,(2*i+1):6);
          count:=count+1;
          If count>=NpL Then
            Begin writeln(f); count:=0 End
        End;
    writeln(f)
  End;

Begin
  a :=3; b := 4;
  writeln('Primzahlberechnung durch Sieb des Eradingsbums');
  writeln;
  REPEAT
     write('Maximum: '); readln(m)
  UNTIL (m>0) and (m<2*max);
  FOR i:=1 to (m DIV 2) DO
     sieb[i] := TRUE;
  FOR i:=1 TO TRUNC(sqrt(m)+1) DO
    IF sieb[i] THEN
    Begin
       FOR j:=0 TO ((m-1-b) DIV a) DO
          sieb[b+j*a] := FALSE;
       write((2*i+1):8,chr(13));
       i := succ(i);
       a := a + 2;
       b := b + 2*a-2;
   End;
   Ausgabe(output,1,m)
End.