from itertools import repeat izip from math import ceil sqrt from oper

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from itertools import repeat, izip
from math import ceil, sqrt
from operator import eq, mod, truediv
def _candidate_primes(limit):
sqrt_limit = int(ceil(sqrt(limit)))
for x in xrange(1, sqrt_limit):
for y in xrange(1, sqrt_limit):
n = 4*(x**2) + y**2
if n <= limit and (eq(mod(n, 12), 1) or eq(mod(n, 12), 5)):
yield n
n = 3 * (x**2) + y**2
if n <= limit and eq(mod(n, 12), 7):
yield n
n = 3*(x**2) - y**2
if n <= limit and x > y and eq(mod(n, 12), 11):
yield n
def atkins_sieve(limit):
isprime = dict(izip((xrange(5, limit)), repeat(False, limit - 5)))
for x in _candidate_primes(limit):
try:
isprime[x] = not isprime[x]
except IndexError:
continue
yield 2
yield 3
for key in sorted(isprime.keys()):
if isprime[key]:
yield key
for x in range(key**2, limit, key**2):
isprime[x] = False