• API
• FAQ
• Tools
• Archive
A Pastebin account makes a great Christmas gift
SHARE
TWEET

# Untitled

a guest Jan 12th, 2018 51 Never
ENDING IN00days00hours00mins00secs

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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top