4 February 2016

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]]

0 comments:

Post a Comment

Thank you for comment. We will try to enhance the quality of this website.