{{ message }}

Instantly share code, notes, and snippets.

# JimDennis/eratosthenes_sieve.py

Created Jan 5, 2018
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))