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_sie
(num: int)
| 3 | |
| 4 | |
| 5 | def odd_sieve(num: int) -> list[int]: |
| 6 | """ |
| 7 | Returns the prime numbers < `num`. The prime numbers are calculated using an |
| 8 | odd sieve implementation of the Sieve of Eratosthenes algorithm |
| 9 | (see for reference https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). |
| 10 | |
| 11 | >>> odd_sieve(2) |
| 12 | [] |
| 13 | >>> odd_sieve(3) |
| 14 | [2] |
| 15 | >>> odd_sieve(10) |
| 16 | [2, 3, 5, 7] |
| 17 | >>> odd_sieve(20) |
| 18 | [2, 3, 5, 7, 11, 13, 17, 19] |
| 19 | """ |
| 20 | |
| 21 | if num <= 2: |
| 22 | return [] |
| 23 | if num == 3: |
| 24 | return [2] |
| 25 | |
| 26 | # Odd sieve for numbers in range [3, num - 1] |
| 27 | sieve = bytearray(b"\x01") * ((num >> 1) - 1) |
| 28 | |
| 29 | for i in range(3, int(sqrt(num)) + 1, 2): |
| 30 | if sieve[(i >> 1) - 1]: |
| 31 | i_squared = i**2 |
| 32 | sieve[(i_squared >> 1) - 1 :: i] = repeat( |
| 33 | 0, ceil((num - i_squared) / (i << 1)) |
| 34 | ) |
| 35 | |
| 36 | return [2, *list(compress(range(3, num, 2), sieve))] |
| 37 | |
| 38 | |
| 39 | if __name__ == "__main__": |