[NBLUG/talk] OT: Primes .. Sieve of Erastothanes

mrp mrp at sonic.net
Thu Jun 5 19:28:01 PDT 2003


For my compiler design class we had to implement a compiler for the 
toy language PL.  (Created by Dijkstra to illustrate his gaurded command
idea.)  The language looks like a crippled version of pascal, and 
for most purposes it is.

All this talk of primes got me thinking about implementing a 
sieve of Erastothanes in PL.. so I did: (translating this to a 
"real" language is left as an exercise to the reader.)

$ sieve of erastothanes
begin
  const max = 3000;
  Boolean array p[max];
  proc sieve
  begin
    proc init
    begin  
      integer i;

      p[1] := false; $ 1 is never prime
      i := 2;

      do
        i < max + 1 -> p[i] := true; i := i + 1;
      od;
    end;
    integer i,j;

    call init;
    i := 1;
    do
      i < max+1 ->
        if
          p[i] -> 
            j := 2 * i;
            do
              j < max+1 ->
                p[j] := false;
                j := j + i;
            od;
            []
          ~p[i] -> skip;
        fi;
        i := i + 1;
    od;
  end;
  integer counter;

  call sieve;

  counter := 1;
  do
    counter < max+1 ->
      if
        p[counter]  ->
          write counter;
          []
        ~p[counter]  ->
          skip;
      fi;
      counter := counter + 1;
  od;
end.



More information about the talk mailing list