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:

  1. Create a list of consecutive integers from 2 to n (the number you are given).
  2. Start with the first number in the list (2). It is a prime, so circle it.
  3. Cross out all multiples of that number (except the number itself).
  4. Move to the next number in the list that is not crossed out. Circle it and cross out all its multiples.
  5. Repeat this process until you have circled all numbers and crossed out all their multiples up to n.
  6. 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!

Geek
Inputs

Arg 1:

10
Expected Output
[2, 3, 5, 7]
Actual Output
Sieve of Eratosthenes [advanced] | Coding for Kids