# 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)))
 

CiMgUHl0aG9uIHRyYW5zbGF0aW9uIG9mIGh0dHA6Ly8gcHJpbWVzaWV2ZS5vcmcvc2VnbWVudGVkX3NpZXZlLmh0bWwKCkNBQ0hFX1NJWkUgPSAzMjc2OAoKCmRlZiBzZWdtZW50ZWRfc2lldmUobGltaXQsIHNlZ21lbnRfc2l6ZT1DQUNIRV9TSVpFKToKICAgIHNxcnQgPSBpbnQobGltaXQgKiogMC41KQogICAgY291bnQgPSAwIGlmIGxpbWl0IDwgMiBlbHNlIDEKICAgIHMsIG4gPSAyLCAzCiAgICBzaWV2ZSA9IFtdCiAgICBpc19wcmltZSA9IFtUcnVlXSAqIChzcXJ0ICsgMSkKICAgICMgZ2VuZXJhdGUgc21hbGwgcHJpbWVzIDw9IHNxcnQKICAgIGkgPSAyCiAgICB3aGlsZSBpICogaSA8PSBzcXJ0OgogICAgICAgIGlmIGlzX3ByaW1lW2ldOgogICAgICAgICAgICBqID0gaSAqIGkKICAgICAgICAgICAgd2hpbGUgaiA8PSBzcXJ0OgogICAgICAgICAgICAgICAgaXNfcHJpbWVbal0gPSAwCiAgICAgICAgICAgICAgICBqICs9IGkKICAgICAgICBpICs9IDEKICAgIHByaW1lcyA9IFtdCiAgICBuZXh0ID0gW10KICAgIHlpZWxkIDIKICAgIGxvdyA9IDAKICAgIHdoaWxlIGxvdyA8PSBsaW1pdDoKICAgICAgICBzaWV2ZSA9IFsxXSAqIHNlZ21lbnRfc2l6ZQogICAgICAgICMgY3VycmVudCBzZWdtZW50ID0gaW50ZXJ2YWwgW2xvdywgaGlnaF0KICAgICAgICBoaWdoID0gbWluKGxvdyArIHNlZ21lbnRfc2l6ZSAtIDEsIGxpbWl0KQogICAgICAgICMgc3RvcmUgc21hbGwgcHJpbWVzIG5lZWRlZCB0byBjcm9zcyBvZmYgbXVsdGlwbGVzCiAgICAgICAgd2hpbGUgcyAqIHMgPD0gaGlnaDoKICAgICAgICAgICAgaWYgaXNfcHJpbWVbc106CiAgICAgICAgICAgICAgICBwcmltZXMuYXBwZW5kKHMpCiAgICAgICAgICAgICAgICBuZXh0LmFwcGVuZChzICogcyAtIGxvdykKICAgICAgICAgICAgcyArPSAxCiAgICAgICAgIyBzaWV2ZSB0aGUgY3VycmVudCBzZWdtZW50CiAgICAgICAgaSA9IDEKICAgICAgICB3aGlsZSBpIDwgbGVuKHByaW1lcyk6CiAgICAgICAgICAgIGogPSBuZXh0W2ldCiAgICAgICAgICAgIGsgPSBwcmltZXNbaV0gKiAyCiAgICAgICAgICAgIHdoaWxlIGogPCBzZWdtZW50X3NpemU6CiAgICAgICAgICAgICAgICBzaWV2ZVtqXSA9IDAKICAgICAgICAgICAgICAgIGogKz0gawogICAgICAgICAgICBuZXh0W2ldID0gaiAtIHNlZ21lbnRfc2l6ZQogICAgICAgICAgICBpICs9IDEKICAgICAgICB3aGlsZSBuIDw9IGhpZ2g6CiAgICAgICAgICAgIGlmIHNpZXZlW24gLSBsb3ddOiAgIyBuIGlzIGEgcHJpbWUKICAgICAgICAgICAgICAgIHlpZWxkIG4KICAgICAgICAgICAgICAgIGNvdW50ICs9IDEKICAgICAgICAgICAgbiArPSAyCiAgICAgICAgbG93ICs9IHNlZ21lbnRfc2l6ZQoKCnByaW50ICJwcmltZXMgZm91bmQ6IiwgbGVuKGxpc3Qoc2VnbWVudGVkX3NpZXZlKDEwNDcyOSkpKQo=