Sieve of Eratosthenes: Ruby and Python

Here's a bit more math history and coding nonsense, this time involving prime numbers...

Eratosthenes was a Greek mathematician and one of the greatest scholars of Alexandria (273-192 B.C). He derived an algorithm for sifting out the composite numbers in the natural series, leaving only prime numbers remaining. The algorithm works like this:

1. Start with a list of all the odd numbers in order, starting from 3.
2. Cancel the successive multiples for each element, one after another.
3. Continue iterating through the list until you reach the end.

As usual, just for fun, I coded up the Sieve of Eratosthenes in Ruby and Python. Here, we start with a list of natural numbers in order, beginning with the first prime number, 2. The sieve logic then examines each element of the list, and if the value of the list element in question is less than the square root of the maximum value in the list, then we proceed to remove all multiples of this list element, starting from the square of this element and working upwards through the end of the list. Such an approach increases efficiency a bit so that we do not have to check all elements up through to the end of the list when searching for multiples to sift out.


In Ruby

def execute(limit=100)
  # set up
  primes = (2..limit).to_a

  # sieve logic
  sieve_end = Math.sqrt(limit).floor
  for i in 0...primes.size
    break if primes[i] > sieve_end
    primes.delete_if { |n| n >= primes[i]**2 && n%primes[i]==0 }
  end

  primes
end

In Python

def sublime(m):
   return lambda x: x==m or (x>m and x%m!=0)

def execute(limit=100):
   # set-up
   primes = range(2,limit+1)

   # sieve logic
   sieve_end = int(sqrt(limit))

   for i in range(0, len(primes)):
       if primes[i] > sieve_end: break
       primes[i:] = filter(sublime(primes[i]), primes)

   return primes

While the code above may offend pure Rubyists and Pythonistas, it nevertheless appeals to me for still being rather clean. I tried to use more a more functional programming approach, with a nice Ruby block and a Python lambda function for sifting out the non-primes.

I haven't been coding any Java seriously for the past few months, and I don't seem to miss Java much. I must admit that functional programming seems quite fresh and interesting, and both Ruby and Python have features that allow for a functional approach mapping, reducing, and filtering lists.

Wonder if I should try this in CLisp tonight?