TheAlgorithms-Python

1
"""Segmented Sieve."""
2

3
import math
4

5

6
def sieve(n: int) -> list[int]:
7
    """
8
    Segmented Sieve.
9

10
    Examples:
11
    >>> sieve(8)
12
    [2, 3, 5, 7]
13

14
    >>> sieve(27)
15
    [2, 3, 5, 7, 11, 13, 17, 19, 23]
16

17
    >>> sieve(0)
18
    Traceback (most recent call last):
19
        ...
20
    ValueError: Number 0 must instead be a positive integer
21

22
    >>> sieve(-1)
23
    Traceback (most recent call last):
24
        ...
25
    ValueError: Number -1 must instead be a positive integer
26

27
    >>> sieve(22.2)
28
    Traceback (most recent call last):
29
        ...
30
    ValueError: Number 22.2 must instead be a positive integer
31
    """
32

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

37
    in_prime = []
38
    start = 2
39
    end = int(math.sqrt(n))  # Size of every segment
40
    temp = [True] * (end + 1)
41
    prime = []
42

43
    while start <= end:
44
        if temp[start] is True:
45
            in_prime.append(start)
46
            for i in range(start * start, end + 1, start):
47
                temp[i] = False
48
        start += 1
49
    prime += in_prime
50

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

54
    while low <= n:
55
        temp = [True] * (high - low + 1)
56
        for each in in_prime:
57
            t = math.floor(low / each) * each
58
            if t < low:
59
                t += each
60

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

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

68
        low = high + 1
69
        high = min(high + end, n)
70

71
    return prime
72

73

74
if __name__ == "__main__":
75
    import doctest
76

77
    doctest.testmod()
78

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