# Python translation of http:// primesieve.org/segmented_sieve.html

CACHE_SIZE = 32768


def segmented_sieve(limit, segment_size=CACHE_SIZE):
    sqrt = int(limit ** 0.5)
    count = 0 if limit < 2 else 1
    s, n = 2, 3
    sieve = []
    is_prime = [True] * (sqrt + 1)
    # generate small primes <= sqrt
    i = 2
    while i * i <= sqrt:
        if is_prime[i]:
            j = i * i
            while j <= sqrt:
                is_prime[j] = 0
                j += i
        i += 1
    primes = []
    next = []
    yield 2
    low = 0
    while low <= limit:
        sieve = [1] * segment_size
        # current segment = interval [low, high]
        high = min(low + segment_size - 1, limit)
        # store small primes needed to cross off multiples
        while s * s <= high:
            if is_prime[s]:
                primes.append(s)
                next.append(s * s - low)
            s += 1
        # sieve the current segment
        i = 1
        while i < len(primes):
            j = next[i]
            k = primes[i] * 2
            while j < segment_size:
                sieve[j] = 0
                j += k
            next[i] = j - segment_size
            i += 1
        while n <= high:
            if sieve[n - low]:  # n is a prime
                yield n
                count += 1
            n += 2
        low += segment_size


print "primes found:", len(list(segmented_sieve(104729)))