segmented sieve import math def sieven int listint if n 0 or isinstancen float msg fnumber n must instead be a positive integer raise valueerrormsg inprime start 2 end intmath sqrtn size of every segment temp true end 1 prime while start end if tempstart is true inprime appendstart for i in rangestart start end 1 start tempi false start 1 prime inprime low end 1 high min2 end n while low n temp true high low 1 for each in inprime t math floorlow each each if t low t each for j in ranget high 1 each tempj low false for j in rangelentemp if tempj is true prime appendj low low high 1 high minhigh end n return prime if name main import doctest doctest testmod printfsieve106 segmented sieve examples sieve 8 2 3 5 7 sieve 27 2 3 5 7 11 13 17 19 23 sieve 0 traceback most recent call last valueerror number 0 must instead be a positive integer sieve 1 traceback most recent call last valueerror number 1 must instead be a positive integer sieve 22 2 traceback most recent call last valueerror number 22 2 must instead be a positive integer size of every segment
import math


def sieve(n: int) -> list[int]:
    

    if n <= 0 or isinstance(n, float):
        msg = f"Number {n} must instead be a positive integer"
        raise ValueError(msg)

    in_prime = []
    start = 2
    end = int(math.sqrt(n))  
    temp = [True] * (end + 1)
    prime = []

    while start <= end:
        if temp[start] is True:
            in_prime.append(start)
            for i in range(start * start, end + 1, start):
                temp[i] = False
        start += 1
    prime += in_prime

    low = end + 1
    high = min(2 * end, n)

    while low <= n:
        temp = [True] * (high - low + 1)
        for each in in_prime:
            t = math.floor(low / each) * each
            if t < low:
                t += each

            for j in range(t, high + 1, each):
                temp[j - low] = False

        for j in range(len(temp)):
            if temp[j] is True:
                prime.append(j + low)

        low = high + 1
        high = min(high + end, n)

    return prime


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    print(f"{sieve(10**6) = }")