Sieve of Eratosthenes
Advanced
Welcome to the magical world of prime numbers! Today, you are going to learn to make a simple but mighty algorithm called the Sieve of Eratosthenes. This algorithm helps you find all the prime numbers up to a given number.
Prime numbers are numbers greater than 1 that are only divisible by 1 and themselves. The Sieve of Eratosthenes is an ancient method that efficiently finds all prime numbers up to a specific number by "sifting" out the non-primes.
Here's how it works:
- Create a list of consecutive integers from 2 to
n(the number you are given). - Start with the first number in the list (2). It is a prime, so circle it.
- Cross out all multiples of that number (except the number itself).
- Move to the next number in the list that is not crossed out. Circle it and cross out all its multiples.
- Repeat this process until you have circled all numbers and crossed out all their multiples up to
n. - All the circled numbers are the primes up to
n.
Your task is to implement the function sieve_of_eratosthenes(n: int) -> list: that returns a list of prime numbers up to and including n. Let's see some examples:
sieve_of_eratosthenes(10) # Returns: [2, 3, 5, 7] sieve_of_eratosthenes(20) # Returns: [2, 3, 5, 7, 11, 13, 17, 19] sieve_of_eratosthenes(5) # Returns: [2, 3, 5]
Now, it's your turn to help find those primes and become a number magician!
Inputs
Arg 1:
10Expected Output
[2, 3, 5, 7]Actual Output