PROGRAM Prime3(Output);
    {-------------------------------------------
      program 8.5 - Generates the primes between
      3...10000 using a sieve containing odd
      integers in this range
    --------------------------------------------}

    CONST
        SetSize = 128;      { implementation dependent; >= 2}
        MaxElement = 127;   { SetSize - 1 }
        SetParts = 39;      { = 10000 DIV SetSize DIV 2 }
    TYPE
        Natural = 0..MaxInt;
    VAR
        Sieve, Primes: ARRAY[0..SetParts] OF SET OF 0..MaxElement;
        NextPrime: RECORD
            Part: 0..SetParts;
            Element: 0..MaxElement
        END;
        Multiple, NewPrime: Natural;
        P, N, Count: Natural;
        Empty: Boolean;
BEGIN
    FOR P := 0 TO SetParts DO
    BEGIN
        Sieve[P] := [0..MaxElement];
        Primes[P] := [];
    END;

    Sieve[0] := Sieve[0] - [0];
    Empty := False;
    NextPrime.Part := 0;
    NextPrime.Element := 1;

    WITH NextPrime DO
        REPEAT
            WHILE NOT (Element IN Sieve[Part]) DO
                Element := Succ(Element);

            Primes[Part] := Primes[Part] + [Element];
            NewPrime := 2 * Element + 1;
            Multiple := Element;
            P := Part;

            WHILE P <= SetParts DO
            BEGIN
                Sieve[P] := Sieve[P] - [Multiple];
                P := P + Part * 2;
                Multiple := Multiple + NewPrime;
                WHILE Multiple > MaxElement DO
                BEGIN
                    P := P + 1;
                    Multiple := Multiple - SetSize
                END
            END;

            IF Sieve[Part] = [] THEN
            BEGIN
                Empty := True;
                Element := 0
            END;

            WHILE Empty AND (Part < SetParts) DO
            BEGIN
                Part := Part + 1;
                Empty := Sieve[Part] = []
            END
        UNTIL Empty;

    Count := 0;
    FOR P := 0 TO SetParts DO
        FOR N := 0 TO MaxElement DO
            IF N IN Primes[P] THEN
            BEGIN
                Write(Output, 2 * N + 1 + P * SetSize *2:6);
                Count := Count + 1;
                IF (Count MOD 8) = 0 THEN
                    WriteLn(Output)
            END
END.