A prime number sieve using recursion

Question

Out of curiosity, I built a recursive Sieve of Eratosthenes in Python and I was wondering how it could be improved for efficiency and how it can improved to be aligned with python best practices.

Essentially, there is a recursive function (coded horrendously IMO), filter_multiples, which removes the multiples of some number. Then there is a for loop which cycles through the list which needs to be filtered and uses each number in that list for the recursive function. After the numbers in the list runs out, the code stops and outputs the list which remains i.e. the list of primes. Below is the code:

# Generate odd numbers to filter through, add number 2 after filtering
odd_nums = range(3,100,2)


def filter_multiples(lst, n, counter):
    ''' A recursive method used to remove multiples of n in a list(lst)
        and using a counter to iterate through that list
    '''
    if len(lst) == counter:
        return lst
    else:
        # See if a number in a list is divisble by n and if so, remove it
        if lst[counter] % n == 0 and lst[counter] != n:
            lst.remove(lst[counter])
        if len(lst) == counter:
            return lst
        return filter_multiples(lst, n, counter+1)

# Cycle through the numbers and use filter_multiples to remove the factors and keep the primes
for i in odd_nums:
    filter_multiples(odd_nums, i, 0)

odd_nums.insert(0,2)
print odd_nums

I would like to know how to improve upon the recursive function and furthermore, how to improve my program so that is in line with python best practices.

Answer 1

This is not a Sieve of Eratosthenes for a few reasons.

Instead of just throwing a real one at you, lets see how we can deduce a Sieve of Eratosthenes just by improving the current code.

The first thing to note is that we can clean up the recursive function be removing the return; you're only returning the list they already have.

Secondly, you can remove the else and remove the last if by making the first check stricter. That gives:

def filter_multiples(lst, n, counter):
    ''' A recursive method used to remove multiples of n in a list(lst)
        and using a counter to iterate through that list
    '''
    if len(lst) <= counter:
        return

    # See if a number in a list is divisble by n and if so, remove it
    if lst[counter] % n == 0 and lst[counter] != n:
        lst.remove(lst[counter])

    filter_multiples(lst, n, counter+1)

You then find that the recursive function is easier as a loop:

def filter_multiples(lst, n, counter):
    while counter < len(lst):
        # See if a number in a list is divisble by n and if so, remove it
        if lst[counter] % n == 0 and lst[counter] != n:
            lst.remove(lst[counter])

        counter += 1

If this insistence to use an imperative style makes you confused about what the point of recursion is, let me assure you there are uses. Traversing tree data structures is traditionally done recursively. Here's some example of that. It's not, however, good to use recursion for the sake of it unless using a language specifically designed to do so.

This uses remove repeatedly to filter elements. remove is O(n) so the overall time for this is O(n²). You know this can't be a Sieve of Eratosthenes because the whole sieve is meant to be O(n log n)!

One way to improve this is to use a list comprehension:

def filter_multiples(lst, n):
    lst[:] = [i for i in lst if i == n or i % n]

which, you might think, is then better just using return:

def filter_multiples(lst, n):
    return [i for i in lst if i == n or i % n]

However, the outer loop

for i in odd_nums:
    filter_multiples(odd_nums, i)

would be changed to

for i in odd_nums:
    odd_nums = filter_multiples(odd_nums, i)

and this means the for i in odd_nums would be iterating over the old odd_nums. Thus, this needs to be in place with how you've made it. However, modifying the number of elements in lists while you're iterating over them is heavily discouraged. This means that maybe we should think of a different technique for filter_multiples.

One such technique is marking all of the elements to remove and then doing a list comprehension:

for i, val in enumerate(lst):
    if not (val == n or val % n):
        lst[i] = None

lst[:] = [val for val in lst if val is not None]

The advantage of this is that we can hoist the final comprehension outside of the two loops and just skip None in the outer loop:

def filter_multiples(lst, n):
    for i, val in enumerate(lst):
        if val is None:
            continue

        if not (val == n or val % n):
            lst[i] = None

# Cycle through the numbers and use filter_multiples to remove the factors and keep the primes
for val in odd_nums:
    if val is not None:
        filter_multiples(odd_nums, val)

odd_nums = [val for val in odd_nums if val is not None]

This seems more complicated, true, and it's probably also slower than the comprehension because it's looping over more numbers. However, think about this check:

if not (val == n or val % n):
    lst[i] = None

Since we're not compressing lst, val will directly map to a given i (or None). As such, if we work out that mapping we can avoid the check by just going over all the i that map to {2n, 3n, 4n, ...}.

One way of doing that is just making val map to i:

sieve = range(100)
sieve[0] = sieve[1] = None

def filter_multiples(lst, n):
    for i in range(2*n, len(lst), n):
        if lst[i] is None:
            continue

        lst[i] = None

# Cycle through the numbers and use filter_multiples to remove the factors and keep the primes
for val in sieve:
    if val is not None:
        filter_multiples(sieve, val)

sieve = [val for val in sieve if val is not None]

print sieve

In fact, the if is no longer needed inside this loop and we can do:

def filter_multiples(lst, n):
    for i in range(2*n, len(lst), n):
        lst[i] = None

Then you'd probably want to tidy up the code by putting it in a function:

def mask_indicies(lst, start, step):
    for i in range(start, len(lst), step):
        lst[i] = None

def primes_below(maximum):
    sieve = list(range(maximum))
    sieve[0] = sieve[1] = None

    for val in sieve:
        if val is not None:
            mask_indicies(sieve, 2*val, val)

    return [val for val in sieve if val is not None]

if __name__ == "__main__":
    print(primes_below(100))

That is a Sieve of Eratosthenes. I've added Python 3 compatibility.

---

Note that I have previously talked about doing similar things really fast, first with a Sieve of Sundaram and then comparing it to a Sieve of Eratosthenes (Eratosthenes won).