Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/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))
Add Comment
Please, Sign In to add comment