- Home
- >
- Sieve of Eratosthenes – Prime Number Algorithm

# 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*^{2}, perform an incremental of*p*and mark the integers equal or greater than*p*^{2}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*^{2 }= 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*^{2}=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

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

1 | 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 | 30 |

31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |

41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |

61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |

71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |

81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |

91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

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

1 | 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 | 30 |

31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |

41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |

61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |

71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |

81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |

91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

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

1 | 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 | 30 |

31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |

41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |

61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |

71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |

81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |

91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

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

1 | 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 | 30 |

31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |

41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |

61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |

71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |

81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |

91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

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