--//////////////////////////////////////////////////////////
--// Name: Peter M. Maurer
--// Program: Sieve of Eratosthenes
--// Due: Never
--// Language: Ada
--//////////////////////////////////////////////////////////

with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada.Text_IO, Ada.Integer_Text_IO;

procedure SieveE is

     Candidates : array(0..999) of Integer;
     i : Integer;
     j : Integer;

begin
	-- define the sieve data structure
	for i in 0..999 loop
		-- everything is potentially prime until proven otherwise
		Candidates(i) := 1;
	end loop;
	-- Neither 1 nor 0 is prime, so flag them off
	Candidates(0) := 0;
	Candidates(1) := 0;
	-- start the sieve with the integer 0
	i := 0;
	while i < 1000 loop
		-- advance to the next un-crossed out number.
		-- this number must be a prime
		while (i<1000) and then (Candidates(i) = 0) loop
			i := i+1;
		end loop;
		-- insure against running off the end of the data structure
		if i<1000 then
			-- cross out all multiples of the prime, starting with 2*p.
			j := 2;
      			while (j*i) < 1000 loop
        			Candidates(j*i) := 0;
				j := j + 1;
      			end loop;
			-- advance to the next candidate
			i := i+1;
		end if;
	end loop;
	-- all uncrossed-out numbers are prime (and only those numbers)
	-- print all primes
	for i in 0..999 loop
		if Candidates(i) /= 0 then
		  Put(i,5);
		  Put(" is prime");
		  New_Line;
		end if;
	end loop;
end SieveE;