class SIEVEE

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

creation {ANY}
	make

feature {ANY}
      -- define the sieve data structure
      Candidates: ARRAY[INTEGER]
   make is
      local
         i : INTEGER
         j : INTEGER
      do
         !!Candidates.make(0,1000)
         -- Everything is potentially prime until proven otherwise
         from
	    i := 0
	 until
	    i > 1000
	 loop
	    Candidates.put(1,i)
            i := i + 1
         end
         -- Neither 0, nor 1 is prime
         Candidates.put(0,0)
         Candidates.put(0,1)


         -- start the sieve with the integer 0

         from
            i := 0
         until
            i >= 1000
         loop
            -- advance to the next un-crossed out number.
            -- this number must be a prime
            from
            until
               i >= 1000 or Candidates.item(i) /= 0
            loop
               i := i + 1
            end
            -- 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.
               from
                  j := 2
               until
                  j*i >= 1000
               loop
                   Candidates.put(0,j*i)
                   j := j+1
               end
               -- advance to the next candidate
               i := i + 1
            end
         end
         -- all uncrossed-out numbers are prime (and only those numbers)
         -- print all primes
         from
            i := 0
         until
            i >= 1000
         loop
            if Candidates.item(i) /= 0 then
               io.put_integer(i)
               io.put_string(" is prime%N")
            end
            i := i + 1
         end
      end
end