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
import math


def sieve(n: int) -> list[int]:
    """
    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
    """

    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))  # Size of every segment
    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) = }")
