Sieve of Eratosthenes – Prime Number Algorithm

Sieve of EratosthenesSieve 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 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.

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 (32 = 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 52=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.
12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • Step 2: The next step is to write in bold all the multiples of 2, except 2 itself.
12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • Step 3: Now bold all multiples of 3, 5, and 7 and only leave these numbers.
12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • 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.
12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • 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.

Practice Questions

1. Which of the following is a prime number?

2. Which of the following is a prime number?

3. Which of the following is a prime number?

4. True or False: The number, $101$, is  a prime number.

5. True or False: The number, $207$, is  a prime number.


 

Previous Lesson | Main Page | Next Lesson