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.