Python/maths/segmented_sieve.py at master · ivan53/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
"""Segmented Sieve."""

importmath


defsieve(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
 """

ifn<=0orisinstance(n, float):
msg=f"Number {n} must instead be a positive integer"
raiseValueError(msg)

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

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

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

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

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

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

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

returnprime


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{sieve(10**6) =}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
"""Segmented Sieve."""

importmath


defsieve(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
 """

ifn<=0orisinstance(n, float):
msg=f"Number {n} must instead be a positive integer"
raiseValueError(msg)

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

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

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

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

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

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

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

returnprime


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{sieve(10**6) =}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
"""Segmented Sieve."""

importmath


defsieve(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
 """

ifn<=0orisinstance(n, float):
msg=f"Number {n} must instead be a positive integer"
raiseValueError(msg)

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

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

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

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

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

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

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

returnprime


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{sieve(10**6) =}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
"""Segmented Sieve."""

importmath


defsieve(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
 """

ifn<=0orisinstance(n, float):
msg=f"Number {n} must instead be a positive integer"
raiseValueError(msg)

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

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

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

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

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

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

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

returnprime


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{sieve(10**6) =}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
"""Segmented Sieve."""

importmath


defsieve(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
 """

ifn<=0orisinstance(n, float):
msg=f"Number {n} must instead be a positive integer"
raiseValueError(msg)

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

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

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

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

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

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

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

returnprime


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{sieve(10**6) =}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
"""Segmented Sieve."""

importmath


defsieve(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
 """

ifn<=0orisinstance(n, float):
msg=f"Number {n} must instead be a positive integer"
raiseValueError(msg)

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

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

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

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

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

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

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

returnprime


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{sieve(10**6) =}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
"""Segmented Sieve."""

importmath


defsieve(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
 """

ifn<=0orisinstance(n, float):
msg=f"Number {n} must instead be a positive integer"
raiseValueError(msg)

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

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

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

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

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

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

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

returnprime


if__name__=="__main__":
importdoctest

doctest.testmod()

print(f"{sieve(10**6) =}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
"""Segmented Sieve."""

importmath


defsieve(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
 """

ifn<=0orisinstance(n, float):
msg=f"Number {n} must instead be a positive integer"
raiseValueError(msg)

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

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

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

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

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

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

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

returnprime


if__name__=="__main__":
importdoctest

doctest.testmod()

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