Implementation of Sieve of Eratosthenes in Python

Question

The following is my implementation of Sieve of Eratosthenes. Can somebody please review it? Am I adhering to the algorithm and is it a reasonable implementation of it?

def SieveofEratosthenes(primeseries):

    i=1
    primeserieslist = []
    while(i<primeseries):
        i=i+1
        primeserieslist.append(i)

    x=2

    primeslist = []

    while x <= primeseries and x*2 <= primeseries:
        j=2
        while (j < primeseries):
            z = j*x
            if (z <= primeseries):
                if (z in primeserieslist):
                    primeserieslist.remove(z)
            j = j+1

        x=x+1

    print primeserieslist




SieveofEratosthenes(1000000)

Answer 1

Code review

Advice 1

primeslist is not used. Remove it from your code.

Advice 2

x=2: PEP 8 requires to put two spaces around the operator =.

Advice 3

Also PEP 8 complains about while (j < primeseries):. Those parentheses (()) are not required; remove them in order to reduce the visual clutter.

Advice 4

The identifier primeserieslist is misspelled: it should be prime_series_list. Actually, the role of that very list is to hold the actual prime sieve, so why not rename it simply to sieve?

Advice 5

if (z <= primeseries):
    if (z in primeserieslist):
        primeserieslist.remove(z)

could be written as

if z <= prime_series and z in prime_series_list:
    prime_series_list.remove(z)

Advice 6 SieveofEratosthenes: in Python, CamelCase identifiers are suggested to be used for naming classes. What comes to function naming, your name should be sieve_of_eratosthenes.

Advice 7 x = x + 1: you can write more succinctly x += 1.

Advice 8 Both operations prime_series_list.remove() and z in prime_series_list run in average linear time, and, thus, are inefficient. See below for more efficient implementation.

Alternative implementation

Your implementation works and seems correct, yet there is room for improvement code style -wise and efficiency-wise:

def sieve_of_eratosthenes(max_integer):
    sieve = [True for _ in range(max_integer + 1)]
    sieve[0:1] = [False, False]
    for start in range(2, max_integer + 1):
        if sieve[start]:
            for i in range(2 * start, max_integer + 1, start):
                sieve[i] = False
    primes = []
    for i in range(2, max_integer + 1):
        if sieve[i]:
            primes.append(i)
    return primes

I have set up this benchmark. From it, I get the output:

SieveofEratosthenes in 17560 milliseconds.
sieve_of_eratosthenes in 31 milliseconds.
Algorithms agree: True

Any question? Give me a message.

Answer 2

PEP8 asks that you choose a name like def sieve_of_eratosthenes(). A name like limit would have been more appropriate than primeseries, and naming a list primeserieslist is just redundant, better to call it e.g. candidates or sieve.

In the while loop you might use i += 1, but the whole loop could be replaced with primeserieslist = list(range(1, primeseries)).

This expression:

if (z in primeserieslist):

is very expensive. First please drop the parentheses, if z in primeserieslist: suffices. Second, please understand it is doing a linear scan through a long list, giving you yet another nested loop which will slow you down. Rather than a slow O(n) probe of a list, you want a fast O(1) probe of a set. So the initialization above should be primeserieslist = set(range(1, primeseries)).

Using two tests here is odd:

while x <= primeseries and x*2 <= primeseries:

One test would suffice. Again the while loops might be more clearly described with for running through a range. Your test of whether z is within range should be combined with the while loop's exit criterion.