Week 2.2. Exercise Class - Sieve Of Eratosthenes

Week 2.2. Exercise Class - Sieve of Eratosthenes

What is an algorithm?

An algorithm is a systematic way of solving a problem.
We have seen some already:

• A recipe for a sponge cake
• Calculating quadratic roots using a formula

These are very simple algorithms. We will look at a complicted one and write the code.
You may not understand the code in detail yet. The systematic approach and the high-level idea are important.

The sieve of Eratosthenes

• Eratosthenes was a Greek mathematician (276 BC - 194 BC)
• He notably designed an algorithm for calculating primes.

The idea:

1. Start with a list of numbers from 2 to some bound.
2. The first number in the list is prime.
3. Mark this number as prime.
4. Cross out all multiples of this number.
5. Repeat until everything is crossed out.

Running the algorithm

1. Start with a list of numbers from 2 to some bound (here bound = 55)
2. The first number in the list is prime
   a. mark it as prime
   b. cross out all multiples of that number
3. Repeat the above (2 -> 3) until everything is crossed out.