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 jmaxChk:
        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  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 = 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

StackExchange Code Review Q#51190, answer score: 7