Sieve of Eratosthenes: Representation of Prime Numbers

Sieve of Eratosthenes is an ancient method of finding the prime numbers up to a specific integer. The process involves creating a list of all numbers from 2 to n and crossing out the multiples of each prime number starting from 2, leaving only prime numbers. This method was introduced by a Greek mathematician named Eratosthenes.

Table of Contents

• What are Prime and Composite Numbers?
• What is Sieve of Eratosthenes?
• Key Steps in Sieve of Eratosthenes
• Applications of Sieve of Eratosthenes
• Solved Examples on Sieve of Eratosthenes

What are Prime and Composite Numbers?

Before understanding Sieve of Eratosthenes method we need to know what are prime and composite numbers. Let's learn about prime and composite numbers first:

Prime Numbers: Prime numbers are the numbers which are divisible by only 1 and the number itself are called prime numbers. Prime numbers have only 2 factors.

Composite Numbers: Composite numbers are the numbers that have more than two factors and are called composite numbers.

What is Sieve of Eratosthenes?

The Sieve of Eratosthenes is an effective method to find out the prime numbers between 2 and any number.

Key Steps in Sieve of Eratosthenes

Following are the steps to find out the prime numbers:

• Create a list of consecutive numbers from 2 until n.

• Circle the smallest number.

• Cross out the multiples of that number.

• Circle the next smallest number.

• Cross out the multiples of the circled number.

• Continue till all the numbers are circled or crossed out.

The grid below shows the prime numbers between 2 and 100. The circled numbers are all prime numbers:

 

Applications of Sieve of Eratosthenes

The Sieve of Eratosthenes is a foundational tool in determining distribution and pattern  of prime numbers in mathematics. Apart from mathematics it is also useful in generating large prime numbers for data encryption, and to measure performance of processors in computer science.

Solved Examples on Sieve of Eratosthenes

Example 1: Find all the prime numbers until 30 using Sieve of Eratosthenes method?

Solution: To list all the prime numbers until 30, first create a grid of numbers starting from 2 until 30 and then starting from 2 cross out the multiples of 2 until 30. Circle the remaining numbers to get the final list of prime numbers until 30.

List of all the prime numbers until 30: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

 

Example 2: List the prime numbers up to 10.

Solution: To list all the prime numbers up to 10, list down all the numbers from 2 to 10 and then cancel the multiples of 2 to get the prime numbers.

List of prime numbers up to 10: { 2, 2, 5, 7}

 

Example 3: What are the prime numbers between 2 and 5?

Solution: The only prime number that lies between 2 and 5 is 3.