- Notifications
You must be signed in to change notification settings - Fork 46.7k
/
Copy pathodd_sieve.py
42 lines (32 loc) · 1.01 KB
/
odd_sieve.py
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
fromitertoolsimportcompress, repeat
frommathimportceil, sqrt
defodd_sieve(num: int) ->list[int]:
"""
Returns the prime numbers < `num`. The prime numbers are calculated using an
odd sieve implementation of the Sieve of Eratosthenes algorithm
(see for reference https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).
>>> odd_sieve(2)
[]
>>> odd_sieve(3)
[2]
>>> odd_sieve(10)
[2, 3, 5, 7]
>>> odd_sieve(20)
[2, 3, 5, 7, 11, 13, 17, 19]
"""
ifnum<=2:
return []
ifnum==3:
return [2]
# Odd sieve for numbers in range [3, num - 1]
sieve=bytearray(b"\x01") * ((num>>1) -1)
foriinrange(3, int(sqrt(num)) +1, 2):
ifsieve[(i>>1) -1]:
i_squared=i**2
sieve[(i_squared>>1) -1 :: i] =repeat(
0, ceil((num-i_squared) / (i<<1))
)
return [2, *list(compress(range(3, num, 2), sieve))]
if__name__=="__main__":
importdoctest
doctest.testmod()