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