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.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store