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.