6
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Since you asked "Am I adhering to the algorithm and is it a reasonable implementation of it?", I wanted to point you to this beautiful paper which discusses the very question "when is an implementation of an algorithm faithful to the algorithm" in the specific context of the Sieve Of Eratosthenes: The Genuine Sieve of Eratosthenes by Melissa E. O'Neill, and also the discussion of this paper on Lambda-the-Ultimate. \$\endgroup\$ – Jörg W Mittag Aug 27 '17 at 12:55
  • \$\begingroup\$ @JörgWMittag Thank you so much for pointing to the links. \$\endgroup\$ – Sree Aug 27 '17 at 15:03
8
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you so much for your insightful code review along with your comments. Enormously thankful for identifying the areas of improvement. It will surely take time for comprehending your answer and will make that effort towards understanding it. \$\endgroup\$ – Sree Aug 27 '17 at 8:09
  • \$\begingroup\$ No, PEP8 does not require a space around each binary operator. Actually it contains examples showing the opposite, such as x = x*2 - 1. \$\endgroup\$ – Federico Poloni Aug 27 '17 at 14:55
  • \$\begingroup\$ @FedericoPoloni Thank you for letting me know! I will fix it soon. \$\endgroup\$ – coderodde Aug 27 '17 at 14:56
  • \$\begingroup\$ i have an improvement solution, when you created the sieve list use this to increase performance 'sieve = [True] * (max_integer+1)' instead of list comprehension @coderodde \$\endgroup\$ – Espoir Murhabazi Mar 16 '18 at 9:18
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Note that x in set is O(n) in the worst case. \$\endgroup\$ – Federico Poloni Aug 27 '17 at 14:59
  • \$\begingroup\$ Claiming that the OP will encounter linear cost for testing set membership makes no sense. I think you're referring to hg.python.org/releasing/3.6/file/tip/Objects/setobject.c#l184 . The constant 9 is, I assert, "small", much smaller than N growing without bound in big-O notation. The worst case linear assessment on wiki.python.org/moin/TimeComplexity may be true in some adversarial settings, but the natural numbers do not pose such a setting. The OP will find that the standard hash function will perform nicely. \$\endgroup\$ – J_H Aug 29 '17 at 3:52
  • \$\begingroup\$ I agree with you that this worst case is a highly unlikely one. \$\endgroup\$ – Federico Poloni Aug 29 '17 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.