Returns prime numbers below max_number. See: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes >>> calculate_prime_numbers(10) [2, 3, 5, 7] >>> calculate_prime_numbers(2) []
(max_number: int)
| 39 | |
| 40 | |
| 41 | def calculate_prime_numbers(max_number: int) -> list[int]: |
| 42 | """ |
| 43 | Returns prime numbers below max_number. |
| 44 | See: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes |
| 45 | |
| 46 | >>> calculate_prime_numbers(10) |
| 47 | [2, 3, 5, 7] |
| 48 | |
| 49 | >>> calculate_prime_numbers(2) |
| 50 | [] |
| 51 | """ |
| 52 | |
| 53 | if max_number <= 2: |
| 54 | return [] |
| 55 | |
| 56 | # List containing a bool value for every odd number below max_number/2 |
| 57 | is_prime = [True] * (max_number // 2) |
| 58 | |
| 59 | for i in range(3, isqrt(max_number - 1) + 1, 2): |
| 60 | if is_prime[i // 2]: |
| 61 | # Mark all multiple of i as not prime using list slicing |
| 62 | is_prime[i**2 // 2 :: i] = [False] * ( |
| 63 | # Same as: (max_number - (i**2)) // (2 * i) + 1 |
| 64 | # but faster than len(is_prime[i**2 // 2 :: i]) |
| 65 | len(range(i**2 // 2, max_number // 2, i)) |
| 66 | ) |
| 67 | |
| 68 | return [2] + [2 * i + 1 for i in range(1, max_number // 2) if is_prime[i]] |
| 69 | |
| 70 | |
| 71 | def slow_solution(max_number: int = 10**8) -> int: |
no outgoing calls
no test coverage detected