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 primeI 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
sieve[i*i: n+1:i]
??
>>> 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]
>>>