The Sieve of Eratosthenes is one of a number of prime number sieves. Here’s my implementation in Groovy, comments on how this could be improved are very welcome.

//find all prime number up to max using Sieve of Eratosthenes
//http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
def allprimes(max) {
  def nums = [:]
  for (i in 2..max) {
    nums.put(i,0) //all zeroed (un-marked) at start
  }

  def step = 2
  while (step < max) {
    def i = step+step
    while (i <= max) {
      nums.put(i,1) //mark as non-prime
      i += step
    } 

    //find first unmarked number > step
    if (step+step > max) {
  	  break //no more
    }
    for (lp in step+1..max) {
      if (nums.get(lp) == 0) {
        step = lp //step value is next unmarked
        break
      }
    }
  }

  //return list of all unmarked entries
  def result = []
  for (i in nums) {
    if (i.value == 0) {
      result.add(i.key)
    }
  }
  return result
}

assert allprimes(100) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
assert allprimes(10) == [2, 3, 5, 7]
assert allprimes(2) == [2]

I’m using this to help solve some of the Project Euler questions that use primes.