I've implemented the sieve of Eratosthenes in Python 3 as follows:
def sieve_of_eratosthenes(n): is_prime = [True] * (n+1) is_prime = False is_prime = False p = 0 while True: for i, prime in enumerate(is_prime): if prime and i > p: p = i break else: break multiple = p + p while multiple <= n: is_prime[multiple]= False multiple = multiple + p r =  for i, prime in enumerate(is_prime): if prime: r.append(i) return r
Running this to 100,000 takes ~25 seconds.
I felt that was on the slow side, so I decided to take a different approach. The Sieve works prospectivly: it works ahead to clear out all multiples. I made a retrospective function, trial-dividing everything lower than the current prime-candidate:
def retrospect(n): primes = [2, 3] i = 5 while i <= n: isprime = True lim = math.sqrt(n)+1 for p in primes: if p > lim: break if i % p == 0: isprime = False break if isprime: primes.append(i) i += 2 return primes
This is way faster!
- Are there any obvious shortcomings to the Sieve implementation?
- Is there a point where the retrospect gets slower than the sieve?