# distutils: language=c++

from cython.operator cimport dereference
from libcpp.unordered_map cimport unordered_map


def primes():
    # Yield first two primes
    yield 2
    yield 3

    # Initialize composite lookup
    cdef unordered_map[int, int] composites

    # Initialize the inner generator
    prime_gen = primes()
    next(prime_gen)
    next(prime_gen)
    cdef int next_prime = 3
    cdef int next_square = 9

    # Loop over candidates
    cdef int candidate = 3
    cdef int step, next_composite
    while True:
        candidate += 2

        # Reached next prime square
        if candidate == next_square:
            step = 2 * next_prime
            composites[candidate + step] = step
            next_prime = next(prime_gen)
            next_square = next_prime * next_prime
            continue

        # Reached a prime
        iterator = composites.find(candidate)
        if iterator == composites.end():
            yield candidate
            continue

        # Reached a composite
        composites.erase(iterator)
        step = dereference(iterator).second
        next_composite = candidate + step
        while composites.count(next_composite):
            next_composite += step
        composites[next_composite] = step