# segmented sieve of eratosthenes

from math import sqrt

def primes(n):
    ps, sieve = [], [True] * (n)
    for p in range(2, n):
        if sieve[p]:
            ps.append(p)
            for i in range(p*p, n, p):
                sieve[i] = False
    return ps

def primesRange(lo, hi, delta):
    def qInit(p): return ((lo + p + 1) / -2) % p
    def qReset(p, q): return (q - delta) % p
    output, sieve = [], [True] * delta
    ps = primes(int(sqrt(hi)))[1:]
    qs = map(qInit, ps)
    while lo < hi:
        for i in range(0, delta):
            sieve[i] = True
        for p, q in zip(ps, qs):
            for i in range(q, delta, p):
                sieve[i] = False
        qs = map(qReset, ps, qs)
        for i, t in zip(range(0, delta), range(lo+1, hi, 2)):
            if sieve[i]: output.append(t)
        lo += (2 * delta)
    return output

print primesRange(100, 200, 10)

IyBzZWdtZW50ZWQgc2lldmUgb2YgZXJhdG9zdGhlbmVzCgpmcm9tIG1hdGggaW1wb3J0IHNxcnQKCmRlZiBwcmltZXMobik6CiAgICBwcywgc2lldmUgPSBbXSwgW1RydWVdICogKG4pCiAgICBmb3IgcCBpbiByYW5nZSgyLCBuKToKICAgICAgICBpZiBzaWV2ZVtwXToKICAgICAgICAgICAgcHMuYXBwZW5kKHApCiAgICAgICAgICAgIGZvciBpIGluIHJhbmdlKHAqcCwgbiwgcCk6CiAgICAgICAgICAgICAgICBzaWV2ZVtpXSA9IEZhbHNlCiAgICByZXR1cm4gcHMKCmRlZiBwcmltZXNSYW5nZShsbywgaGksIGRlbHRhKToKICAgIGRlZiBxSW5pdChwKTogcmV0dXJuICgobG8gKyBwICsgMSkgLyAtMikgJSBwCiAgICBkZWYgcVJlc2V0KHAsIHEpOiByZXR1cm4gKHEgLSBkZWx0YSkgJSBwCiAgICBvdXRwdXQsIHNpZXZlID0gW10sIFtUcnVlXSAqIGRlbHRhCiAgICBwcyA9IHByaW1lcyhpbnQoc3FydChoaSkpKVsxOl0KICAgIHFzID0gbWFwKHFJbml0LCBwcykKICAgIHdoaWxlIGxvIDwgaGk6CiAgICAgICAgZm9yIGkgaW4gcmFuZ2UoMCwgZGVsdGEpOgogICAgICAgICAgICBzaWV2ZVtpXSA9IFRydWUKICAgICAgICBmb3IgcCwgcSBpbiB6aXAocHMsIHFzKToKICAgICAgICAgICAgZm9yIGkgaW4gcmFuZ2UocSwgZGVsdGEsIHApOgogICAgICAgICAgICAgICAgc2lldmVbaV0gPSBGYWxzZQogICAgICAgIHFzID0gbWFwKHFSZXNldCwgcHMsIHFzKQogICAgICAgIGZvciBpLCB0IGluIHppcChyYW5nZSgwLCBkZWx0YSksIHJhbmdlKGxvKzEsIGhpLCAyKSk6CiAgICAgICAgICAgIGlmIHNpZXZlW2ldOiBvdXRwdXQuYXBwZW5kKHQpCiAgICAgICAgbG8gKz0gKDIgKiBkZWx0YSkKICAgIHJldHVybiBvdXRwdXQKCnByaW50IHByaW1lc1JhbmdlKDEwMCwgMjAwLCAxMCk=