Prime Number Generator in Python using Sieve Method

I have implemented a prime number generator in Python using Sieve of Eratosthenes. Here is my code:
import math

high = 10000
root = int(math.sqrt(high) + 1.0)

ara = [x % 2 for x in xrange(0, high)]

ara[1] = 0
ara[2] = 1

x = 3
while x <= root:        
    if ara[x]:
        z = x * x
        while z < high:             
            ara[z] = 0
            z += (x + x)        
    x += 2
        
prime = [x for x in xrange(2, len(ara)) if ara[x] == 1]
print prime
I am looking for ideas to make my code faster. I tested my Python program using the code for solving a problem named Prime Generator in SPOJ. I could solve the problem correctly that took 3 seconds time and 3.8 MB memory. I am posting another code I found here. This one is similar implementation to mine but more Pythonic and much faster:
nroot = int(math.sqrt(n))
sieve = [True] * (n+1)
sieve[0] = False
sieve[1] = False

for i in xrange(2, nroot+1):
    if sieve[i]:
        m = n/i - i
        sieve[i*i: n+1:i] = [False] * (m+1)

sieve = [i for i in xrange(n+1) if sieve[i]]
I updated the above code and now it's 20% faster! :)
nroot = int(math.sqrt(n))
sieve = [True] * (n+1)
sieve[0] = False
sieve[1] = False
sieve[4: n+1:2] = [False] * (n / 2 - 1)
for i in xrange(2, nroot+1):
    if sieve[i]:
        m = (n/i - i) / 2
        sieve[i*i: n+1:i+i] = [False] * (m+1)

sieve = [i for i in xrange(n+1) if sieve[i]]

Comments

You can replace the multiplication in the inner loop (z = x * y) with addition. Initialize z with x*x and then add (x+x) in each loop.
Tamim Shahriar said…
Thanks, modified the code.
Btw, your 'incrementing x twice' trick is nice. I never thought about it before. It prevents flagging even numbers in the inner loop.
opodarrtho said…
what is the meaning of this line:

sieve[i*i: n+1:i]

??
Tamim Shahriar said…
It means every i-th element in the list starting form i*i and ending in n+1. Check the example:

>>> li = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> li[0:10:2]
[1, 3, 5, 7, 9]
>>> li[3:10:2]
[4, 6, 8, 10]
>>> li[3:9:4]
[4, 8]
>>>

Popular posts from this blog

Strip HTML tags using Python

lambda magic to find prime numbers

Convert text to ASCII and ASCII to text - Python code