sieve of eresthossis cp c++

The Sieve of Eratosthenes is an algorithm used to find all prime numbers up to a given limit. It follows a step-by-step process to identify and mark the prime numbers.

  1. Create a boolean array of size n+1, where n is the given limit. Initialize all elements of the array to true.
  2. Start with the smallest prime number, 2.
  3. Iterate through the array and mark all the multiples of 2 as false, as they cannot be prime.
  4. Find the next prime number, which is the next index in the array that is still marked as true.
  5. Repeat steps 3 and 4 until the square of the current prime number is greater than n. This is because all the non-prime numbers less than or equal to n will have been marked by this point.
  6. The numbers that are still marked as true in the array are the prime numbers.

Here is an example to illustrate the steps:

Let's find all prime numbers up to 20 using the Sieve of Eratosthenes:

  1. Create a boolean array of size 21, initialized with all true values: [true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true].

  2. Start with the smallest prime number, 2.

  3. Mark all the multiples of 2 as false: [true, true, true, true, false, true, false, true, false, true, false, true, false, true, false, true, false, true, false, true, false].

  4. Find the next prime number, which is 3.

  5. Mark all the multiples of 3 as false: [true, true, true, true, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false].

  6. Find the next prime number, which is 5.

  7. Mark all the multiples of 5 as false: [true, true, true, true, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false].

  8. Find the next prime number, which is 7.

  9. Mark all the multiples of 7 as false: [true, true, true, true, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false].

  10. The square of 7 is greater than 20, so we stop here.

  11. The numbers that are still marked as true in the array are the prime numbers: 2, 3, 5, 7, 11, 13, 17, 19.

These are the prime numbers up to 20 using the Sieve of Eratosthenes.