# Sieve of Eratosthenes

## Algorithm :

• List all consecutive numbers from 2 to η, i.e. (2, 3, 4, 5, ……, η).
• Assign the first prime number-letter p.
• Beginning with p2, perform an incremental of p and mark the integers equal or greater than p2 in the algorithm. These integers will be p(p + 1), p(p + 2), p(p + 3), p(p + 4) …
• The first unmarked number greater than p is identified from the list. If the number does not exist in the list, the procedure is halted. p is equated to the number and step 3 is repeated.
• The Sieve of Eratosthenes is stopped when the square of the number being tested exceeds the last number on the list.
• All numbers in the list left unmarked when the algorithm ends are referred to as prime numbers.
• Step 1: The first step is to list all the numbers.
• Step 2: Write in bold all multiples of 2, except 2 itself.
• Step 3: The next unshaded number is 3. Write its square (32 = 9) in bold.
• Step 4: Now the third unshaded number is 5. Write its square 52=25 in bold.
• Step 5: The fourth unshaded number is 7 and more than the square root of 30. Therefore, there are no multiples of 7 left since they have been eliminated by 2 and 3 as 14, 28, and 21 respectively. The remaining numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29 are prime.

--

--