Sieve of Eratosthenes - Standard and Optimized implementation I am a Java developer who is taking Python for the first time.

I'm sure this is not at all elegant since I am thinking more in C syntax.

"""
This module contains two implementations of the algorithm Sieve of
Eratosthenes. 
"""

# import ############################################################### import #
import math
import numpy
#
 # fun1 ################################################################# fun1 #
def SieveBasic(n):
 """
 This function runs the basic sieve of eratosthenis algorithm (non-optimized)
 and returns a list of prime numbers. The algorithm is implemented as described @:
 http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Example

 """

 l = list(range(2, n+1))
 isPrime = [True] * (n-1)

 for m,n in enumerate(l):
     currentCheck = n
     for i,x in enumerate(l[m+1:]): #take each number and compare with later numbers
       if x % currentCheck == 0:
            isPrime[i+m+1] = False

 primes = [0,1]
 for i,x in enumerate(isPrime):
     if x==True:
         primes.append(2+i)

 return primes  


 """
 This function generates a list of Js required for optimized sieve of eratosthenis algorithm.

 """
def generateJs(i,n):
    j=i**2  
    if j&lt;n:    
        yield j    

    while j+i&lt;=n:
        j+=i
        yield j


def SieveOptimized(n):
 """
 This function runs the optimized sieve of eratosthenis algorithm 
 and returns a list of prime numbers. The algorithm is implemented as described @:
 http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Implementation

 """
 l = list(range(2, n+1))
 isPrime = [True] * (n+1)
 maxChk = math.sqrt(n) 

 for q,r in enumerate(l):
    if r&gt;maxChk:
        break

    for z in generateJs(r,n): 
       isPrime[z] = False    

 return numpy.where(isPrime)[0] # how cool is this
Style

You code does not follow PEP 8, the usual Python coding convention. You'll find tools such as pep8 (or its online version), pylint, pyflakes or pychecker to check for this and other points that might make your code cleaner, more idiomatic or more correct.

I can't be bothered to break the too long lines nor to fix typos in the comments but I did perform the other changes so make pep8 happy.

The result is :

"""
This module contains two implementations of the algorithm Sieve of
Eratosthenes.
"""

import math
import numpy


def SieveBasic(n):
    """
    This function runs the basic sieve of eratosthenis algorithm (non-optimized)
    and returns a list of prime numbers. The algorithm is implemented as described @:
    http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Example
    """
    l = list(range(2, n+1))
    isPrime = [True] * (n-1)

    for m, n in enumerate(l):
        currentCheck = n
        # take each number and compare with later numbers
        for i, x in enumerate(l[m+1:]):
            if x % currentCheck == 0:
                isPrime[i+m+1] = False

    primes = [0, 1]
    for i, prime in enumerate(isPrime):
        if prime:
            primes.append(2+i)

    return primes


def generateJs(i, n):
    """
    This function generates a list of Js required for optimized sieve of eratosthenis algorithm.
    """
    j = i**2
    if j &lt; n:
        yield j

    while j+i &lt;= n:
        j += i
        yield j


def SieveOptimized(n):
    """
        This function runs the optimized sieve of eratosthenis algorithm
        and returns a list of prime numbers. The algorithm is implemented as described @:
        http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Implementation

    """
    l = list(range(2, n+1))
    isPrime = [True] * (n+1)
    maxChk = math.sqrt(n)

    for q, r in enumerate(l):
        if r &gt; maxChk:
            break

        for z in generateJs(r, n):
            isPrime[z] = False

    return numpy.where(isPrime)[0]


def main():
    """Main function"""
    for n in range(1, 200):
        s1 = SieveBasic(n)
        s2 = SieveOptimized(n).tolist()
        if s1 != s2:
            print n, s1, s2

if __name__ == "__main__":
    main()


Also, the name of generateJs is not so great as it doesn't tell us much.

Correctness

When you write two functions to perform the same thing, it can be a good idea to check that you get the same result on a big set of inputs. Here's what I wrote :

def main():
    """Main function"""
    for n in range(1, 200):
        s1 = SieveBasic(n)
        s2 = SieveOptimized(n).tolist()
        if s1 != s2:
            print n, s1, s2


This shows that the result is different when n is 4, 9, 25, 49, 121, 169. The optimised algorithm consider these values as prime even though they shouldn't (as they are perfect squares - of prime numbers which might have its importance when looking for the fix). Once this is fixed, you can use assert to ensure the results of the two functions are the same.

In your case, the fix is simple : changing if j &lt; n for if j &lt;= n in generateJs :

def generateJs(i, n):
    """
    This function generates a list of Js required for optimized sieve of eratosthenis algorithm.
    """
    j = i**2
    if j &lt;= n:
        yield j

    while j+i &lt;= n:
        j += i
        yield 


0 and 1 shouldn't be considered as primes. Again, fixing this is simple : initialising primes as being primes = [] in the basic function and setting isPrime[0] = isPrime[1] = False in the optimised function.

Improving the code for the optimised version

In generateJs, you can factorise code by writing :

def generateJs(i, n):
    """
    This function generates a list of Js required for optimized sieve of eratosthenis algorithm.
    """
    j = i**2
    while j &lt;= n:
        yield j
        j += i


Interestingly, this now looks a lot like range (or xrange depending on the version of Python you are using). We can get rid of it and write :

Also, you don't need to use enumerate:

def SieveOptimized(n):
    """
        This function runs the optimized sieve of eratosthenis algorithm
        and returns a list of prime numbers. The algorithm is implemented as described @:
        http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Implementation

    """
    l = list(range(2, n+1))
    isPrime = [True] * (n+1)
    isPrime[0] = isPrime[1] = False
    maxChk = math.sqrt(n)

    for r in l:
        if r &gt; maxChk:
            break

        for z in xrange(r*r, n+1, r):
            isPrime[z] = False

    return numpy.where(isPrime)[0]


Now, if you think about it, the list l is not that useful. The point is just to perform a re-indexing : what we are really doing is that we loop starting as 2 and we stop at n (included). We can write this directly : for r in xrange(2, n+1):. The same kind of comment also applies to the "basic" version of the code.

def SieveOptimized(n):
    """
        This function runs the optimized sieve of eratosthenis algorithm
        and returns a list of prime numbers. The algorithm is implemented as described @:
        http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Implementation

    """
    isPrime = [True] * (n+1)
    isPrime[0] = isPrime[1] = False
    maxChk = math.sqrt(n)

    for r in xrange(2, n+1):
        if r &gt; maxChk:
            break

        for z in xrange(r*r, n+1, r):
            isPrime[z] = False

    return numpy.where(isPrime)[0]


Because sqrt(n) + 1 &lt;= n + 1 for any n &gt;= 1, we can use maxChk in the call to range :

def SieveOptimized(n):
    """
        This function runs the optimized sieve of eratosthenis algorithm
        and returns a list of prime numbers. The algorithm is implemented as described @:
        http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Implementation

    """
    isPrime = [True] * (n+1)
    isPrime[0] = isPrime[1] = False

    for r in xrange(2, int(math.sqrt(n))+1):
        for z in xrange(r*r, n+1, r):
            isPrime[z] = False

    return numpy.where(isPrime)[0]


Improving the code for the basic version

Here again, the list l is not that useful. The point is just to perform a re-indexing : what we are really doing is that we loop starting as 2 and we stop at n (included).

You can put a few asserts in your code to double check that we don't really need the values from l as we can compute them.

for m, n in enumerate(l):
    assert m == n-2
    assert n == m+2
    currentCheck = m+2
    # take each number and compare with later numbers
    for i, x in enumerate(l[m+1:]):
        assert x - m - i == 3
        assert x == 3 + m + i
        if x % currentCheck == 0:
            isPrime[i+m+1] = False


Messing a bit with indices, you get :

def SieveBasic(n):
    """
    This function runs the basic sieve of eratosthenis algorithm (non-optimized)
    and returns a list of prime numbers. The algorithm is implemented as described @:
    http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Example
    """
    isPrime = [True] * (n-1)

    for x in range(2, n+1):
        # take each number and compare with later numbers
        for j in range(x+1, n+1):
            if j % x == 0:
                isPrime[j - 2] = False

    primes = []
    for i, prime in enumerate(isPrime):
        if prime:
            primes.append(2+i)

    return primes


And the end of the function can be re-written with a list comprehension :

return [2+i for i, prime in enumerate(isPrime) if prime]


This code is still not optimal but because it corresponds to the "basic" version, I guess there is no need to try to make it too much better.

Additional note

In my code, I've been using range and xrange as I am used to switch between Python 2 and Python 3. Depending on the version you are using, I suggest you have a look online to see more details about this. Just keep in mind that you should try to avoid creating a list when an iterator is enough for you.