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