Instantly share code, notes, and snippets.

# JimDennis/eratosthenes_sieve.py

Created January 5, 2018 12:48
Show Gist options
• Save JimDennis/79506483c22c0c3bd05b503c200b43eb to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/usr/bin/env python2 ''' Eratosthenes sieve ''' from __future__ import print_function import array import time start = time.time() limit = 2*10**6 # Four million sieve = array.array('l',range(limit)) primes = [2] # Start with just first, then append to it n = 0 # Index into current prime being eliminated while n*n < limit: p = primes[n] # Eliminate all multiples of primes[n]: for i in range(p+p,limit, p): sieve[i] = 0 # Find remaining numbers up to new upperbound (current prime squared) for i in range(primes[-1]+1,min(limit, p*p)): # min() to avoid out of bounds access. if sieve[i]: primes.append(sieve[i]) n+=1 elapsed = start - time.time() print(', '.join(['%s' % x for x in primes[:20]]), "...", ', '.join(['%s' % x for x in primes[-10:]])) print("%d primes found in %g seconds" % (len(primes), elapsed))

### JimDennis commented Jan 5, 2018

This can find the first 2 million primes in about 2 seconds on my laptop. It's possible to do better with vectorized operations over NumPy ndarrays; but this is a basis for comparison.

### JimDennis commented Jan 5, 2018

For this particular case the use of array.array over just using a plain list seems to give less than a 2% performance benefit.

A quick and dirty test with the limit set at 20 million gives me 10 seconds for the array.array version and 13 seconds for the list version. So that's about a 25% advantage at that scale.