daily pastebin goal
1%
SHARE
TWEET

Untitled

a guest Jan 12th, 2018 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python2
  2. ''' Eratosthenes sieve
  3. '''
  4. from __future__ import print_function
  5.  
  6. import array
  7. import time
  8.  
  9.  
  10. start = time.time()
  11. limit = 2*10**6                        # Four million
  12. sieve = array.array('l',range(limit))  
  13. primes = [2]                           # Start with just first, then append to it
  14. n = 0                                  # Index into current prime being eliminated
  15.    
  16. while n*n < limit:
  17.     p = primes[n]
  18.     # Eliminate all multiples of primes[n]:
  19.     for i in range(p+p,limit, p):
  20.         sieve[i] = 0
  21.     # Find remaining numbers up to new upperbound (current prime squared)
  22.     for i in range(primes[-1]+1,min(limit, p*p)):  # min() to avoid out of bounds access.
  23.         if sieve[i]:
  24.             primes.append(sieve[i])
  25.     n+=1
  26.  
  27. elapsed = start - time.time()
  28. print(', '.join(['%s' % x for x in primes[:20]]), "...",
  29.       ', '.join(['%s' % x for x in primes[-10:]]))
  30. print("%d primes found in %g seconds" % (len(primes), elapsed))
RAW Paste Data
Top