Sieve of Erotosthenes Function to return all the prime numbers up to a certain number https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes >>> prime_sieve(3) [2] >>> prime_sieve(50) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
(n: int)
| 21 | |
| 22 | |
| 23 | def prime_sieve(n: int) -> list: |
| 24 | """ |
| 25 | Sieve of Erotosthenes |
| 26 | Function to return all the prime numbers up to a certain number |
| 27 | https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes |
| 28 | >>> prime_sieve(3) |
| 29 | [2] |
| 30 | >>> prime_sieve(50) |
| 31 | [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] |
| 32 | """ |
| 33 | is_prime = [True] * n |
| 34 | is_prime[0] = False |
| 35 | is_prime[1] = False |
| 36 | is_prime[2] = True |
| 37 | |
| 38 | for i in range(3, int(n**0.5 + 1), 2): |
| 39 | index = i * 2 |
| 40 | while index < n: |
| 41 | is_prime[index] = False |
| 42 | index = index + i |
| 43 | |
| 44 | primes = [2] |
| 45 | |
| 46 | for i in range(3, n, 2): |
| 47 | if is_prime[i]: |
| 48 | primes.append(i) |
| 49 | |
| 50 | return primes |
| 51 | |
| 52 | |
| 53 | def solution(limit: int = 999_966_663_333) -> int: |