[ont.micro.mac] Eratosthenes sieve

info-mac@utcsrgv.UUCP (info-mac) (04/26/84)

Date: 22 Apr 1984 13:04:56-PST
From: Bob Albrightson <uw-beaver!uw-bluechip!bob>
To: info-mac@sumex-aim
Subject: Eratosthenes sieve



Here is a version of the sieve program that should run faster.  If the
implementaion on the mac is correct then this set should use only 2k bytes.
There is also a possibility that the mac pascal will only handle sets in
chunks of one or two words in length (16 or 32 set elements).  If that is
the case then more coding will be required to handle the sieve 16 or 32
elements at a time in an array.  I hope somebody tries this out.


program eratosthenes(output);

  const  sievemax = 16383;

  type   range = 0..sievemax;

  var    i,j: integer;
	 sieve: set of range;

  begin
    sieve := [1..sievemax];
    i := 2;
    writeln(output, 1);  (* kludge, but a small one *)
    while i <= sievemax do
      begin
	writeln(output, i);
	j := i*2;
	while j < sievemax do
	  begin
	    sieve := sieve - [j];
	    j := j + i
	  end;
	i := succ(i);
	while (not (i in sieve)) and (i <= sievemax) do
	  i := succ(i)
      end
  end.


 -bob	(BOB@WASHINGTON)