Monday, January 19, 2015

The "Unfaithful" Sieve of Eratosthenes

I recently came across this bit of Python code on Stack Overflow, in a post that asked for an elucidation of the lambda predicates involved:

primes = range(2, 20) 
for i in range(2, 8): 
     primes = filter(lambda x: x == i or x % i, primes)

This is basically functional-esque code for something that resembles a naive implementation of the Sieve of Erastothenes. Given an input list of integers to start, the algorithm iterates through a second list of integers and uses the lambda predicates to filter the input list such that only primes remain. (The upper bound of 8 for the second list appears arbitrary; it's also a suboptimal upper bound given the input upper bound of 19, but we can ignore that here.)

As far as a naive implementation goes, it's arguably more elegant in a pure functional form like the following (in Haskell):

sieve          :: [Integer] -> [Integer]
sieve []        = []
sieve (p:xs)    = p : sieve [x | x <- xs, x `mod` p > 0]

The Haskell version can be called like so:

sieve [2..19]

As it turns out, though, this is a sieve by trial division rather than the true Sieve of Eratosthenes. Although the underlying logic is similar, the implementation of the algorithm is sufficiently different that the "unfaithful" sieve suffers from noticeably worse time complexity. A quick Google search immediately brings up literature on the subject: The Genuine Sieve of Eratosthenes.