from math import sqrt def sieve(N): """Sieve of Eratosthenes. Returns primes less than N http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes """ # Set up the array. 2 is the first prime, not 1. ar = range(N) ar = 0 limit = 1 + int(sqrt( N)) for d in xrange(2,limit): if ar[d]: # d is prime! mark off the multiples of d. # note that we can start with d*d instead of 2*d. for j in xrange(d*d,N,d): ar[j] = 0 return [x for x in ar if x]There are several optimizations that people tend to do when they write this algorithm. But, this gets us most of the way. I keep rewriting this function for Project Euler problems, but I should really keep a library of the functions I use, or better yet, use Sage.
Saturday, August 14, 2010
Here is a simple implementation of the Sieve of Eratosthenes in Python.