The Groovy Sieve of Barney

Ok, it's really Eratosthenes', but it's my implementation (in Groovy, of course) along with simple display (in CFML, of course), and can be found here (with full source, of course).  If you just want to see the core sieve, here it is ('bound' is the upper range of the search):

class Node {
    def value
    Node next
    Node prev
    def Node(value) {
        this.value = value
    def remove() {
        next?.prev = prev
        prev?.next = next
    def addAfter(value) {
        def n = new Node(value) = next
        n.prev = this
        next = n
// build the number list
head = new Node(2)
tail = head
if (bound > 2) {
    (3..bound).each{ = new Node(it) = tail
        tail =
// start the actual sieve
end = Math.sqrt(bound)
for (curr = head; curr.value <= end; curr = {
    for (target =; target != null; target = {
        if (target.value % curr.value == 0) {

My initial implementation used an ArrayList for storage just to ensure I had the algorithm correct.  I knew that wouldn't scale because of the abundance of removal operations (and therefore sequential copies), but it's simple.  After that I switched to a linked list implementation using my custom Node class.  This cleaned up the sieve implementation a bit and also made is significantly faster with large sets.  However, I'd expect to see higher memory usage with this version because of the extra pointers.

The example is limited to scanning up to 50K, but with that limitation removed it can scan up to 100k in around 5 seconds, and 500K in about 50 seconds (on my little Celeron server).  The ArrayList implementation took about 11 seconds for 100K, and spun on 500K until I killed it.  Feel free to grab the code and remove the limit on your own hardware if you're curious.

Not really any point to the exercise, but lots of fun to pipe Nightwish into my head for an hour and bang out some "real" code again.  Haven't gotten into pure low-level algorithms like that in a long time.  And Groovy's just fun to write; I never have to wait for my fingers to catch up with my mind because it's so concise.  Whipped up all the CFML first as the main course and the wrote the two implementations for dessert.

4 responses to “The Groovy Sieve of Barney”

  1. duncan

    You should look at Project Euler, it's got lots of math problems where this kind of thing is useful

  2. Project Euler at BarneyBlog

    [...] the comments to my post about my prime sieve from last week, Duncan pointed me to Project Euler, which is a collection of math problems that you [...]

  3. Prime Factorization at BarneyBlog

    [...] needed a prime factorization routine several times, and figured I'd share it as a complement to the sieve I shared last week.  Implemented in Groovy, of course.  Typing is a little strange on first glimpse because Groovy [...]