Sieve of Eratosthenes – Prime Number Algorithm

Sieve of Eratosthenes is a technique formulated by a brilliant Greek mathematician, Eratosthenes, whose efforts greatly contributed to identifying prime numbers.

He contributed a lot to mathematics, and the discovery of sieve was the best he had done in this field. It is a pattern or algorithm that works by eliminating numbers that do not fit in a scenario.

What is Sieve of Eratosthenes?

The Sieve of Eratosthenes is a mathematical algorithm of finding prime numbers between two sets of numbers.

Sieve of Eratosthenes models work by sieving or eliminating given numbers that do not meet a certain criterion. For this case, the pattern eliminates multiples of the known prime numbers.

Prime Number Algorithm

A prime number is a positive integer or a whole number greater than 1, which is only divisible by 1 and itself. The Prime number algorithm is a program used to find prime numbers by sieving or removing composite numbers. The algorithm makes work easier by eliminating complex looping divisions or multiplications.

The following are the steps used to find prime numbers equal or less than a given integer η.

• List all consecutive numbers from 2 to η, i.e. (2, 3, 4, 5, ……, η).
• Assign the first prime number letter p.
• Beginning with p², perform an incremental of p and mark the integers equal or greater than p² 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.

Example 1

Fill all prime numbers less than or equal to 30.

Solution

• Step 1: The first step is to list all the numbers.

2, 3, 4, 5, 6 ,7 ,8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, and 30.

• Step 2: Write in bold all multiples of 2, except 2 itself.

2, 3, 4, 5, 6 , 7 , 8, 9, 10,11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, and 30.

• Step 3: The next unshaded number is 3. Write its square (3² = 9) in bold.

2, 3, 4, 5, 6 , 7 , 8, 9, 10,11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, and 30.

• Step 4: Now the third unshaded number is 5. Write its square 5²=25 in bold.

2, 3, 4, 5, 6 , 7 , 8, 9, 10,11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, and 30.

• 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.

Example 2

Find the prime numbers between 1 and 100 using Eratosthenes algorithm.

Solution

1. Step 1: The numbers between 1 and 100 are listed in the table below.

• Step 2: The next step is to write in bold all the multiples of 2, except 2 itself.

• Step 3: Now bold all multiples of 3, 5, and 7 and only leave these numbers.

• Step 4: Since the multiples of 11, 13, 17, and 19 are not present on the list, 1 is finally shaded because it is not prime.

• Step 5: The unshaded numbers are prime. They include:

2, 3, 5,7, 11, 13,17,19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97.