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.
- Create a boolean array of size n+1, where n is the given limit. Initialize all elements of the array to true.
- Start with the smallest prime number, 2.
- Iterate through the array and mark all the multiples of 2 as false, as they cannot be prime.
- Find the next prime number, which is the next index in the array that is still marked as true.
- 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.
- 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:
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].
Start with the smallest prime number, 2.
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].
Find the next prime number, which is 3.
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].
Find the next prime number, which is 5.
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].
Find the next prime number, which is 7.
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].
The square of 7 is greater than 20, so we stop here.
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.