Sieve of Eratosthenes implementation in Groovy
By Steve Claridge on 2014-03-15.
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.