Mathematicians categorized numbers in different categories such as whole numbers, integers, even numbers, and a few more. One of them is prime numbers. The basic definition of a prime number is a number that has only divisors, one is itself and the other is one. In simple words, if a number that can ONLY be divided by itself AND one is called a prime number. Let's apply this condition on a randomly chosen number. In this example, we will pick the number 12, and our objective is to find whether it is a prime number or not.

The condition is that 12 should only be divided by itself and one. This condition isn't fully satisfied because 12 has different factors as well. At this point, you might be thinking that 12 can be divided by itself and one but then you need to look at the condition again. If a number that can ONLY be divided by itself AND one is called a prime number and in the case of 12, it can not only be divided by itself and one but there are many other factors such as 6 \times 2, 2 \times 6, 3 \times 4, and 4 \times 3. Hence, 12 is not a prime number. Let's pick another number, which is 13. Apply the condition and think whether 13 is a prime number or not? If your answer is yes then congratulations! You know what a prime number is. If we look at the factors of 13 which are 13 \times 1, 1 \times 13. Hence, 13 is a prime number.

We can judge many numbers with the help of this condition but there is one number which creates a lot of conflicts and that is 1. The question is whether 1 is a prime number or not? The answer is no because we take 1 has only one divisor. The condition speaks of two divisors and in the case of 1, there is only one divisor which is 1 and that is why 1 is not a prime number.

To find out if a number is prime, orderly divide by prime numbers less than it. When there is no exact division result(meaning remainder is not zero), it is said that the number is prime.

FOR EXAMPLE:

Find if 17 is a prime number or not?

Numbers below 17 and are prime numbers = 2, 3 ,5, 7, 11, 13

\frac { 17 }{ 2 } = 8.5

\frac { 17 }{ 3 } = 5.666

\frac { 17 }{ 5 } = 3.40

\frac { 17 }{ 11 } = 1.545

\frac { 17 }{ 13 } = 1.307

Hence, we can conclude that 17 is a prime number not a composite number.

ERATOSTHENES SIEVE

The sieve of Eratosthenes is an algorithm that allows one to find all the prime numbers less than a given natural number. This algorithm works by eliminating composite numbers by multiplying each prime number with a series of numbers and eliminating those numbers. The multiplication generates a series of numbers (including that prime number) which has a constant difference.

How To use Eratosthenes Sieve

Using Eratosthenes Sieve is very easy once you understand it. Below are some key points that will help you to use Eratosthenes Sieve:

  • Start with a list of numbers ranging from 2 up to a certain number.
  • Eliminate the multiples of 2 from the list.
  • Then, take the first number after the 2 that was not eliminated. In this case, (3) and eliminate their multiples from the list, and so on.
  • The process ends when the square of the largest number confirmed as a prime number is less than the final number on the list.
  • At this point, the numbers that remain on the list are prime numbers.
The best Maths tutors available
1st lesson free!
Intasar
4.9
4.9 (23 reviews)
Intasar
£42
/h
1st lesson free!
Matthew
5
5 (17 reviews)
Matthew
£25
/h
1st lesson free!
Dr. Kritaphat
4.9
4.9 (6 reviews)
Dr. Kritaphat
£49
/h
1st lesson free!
Paolo
4.9
4.9 (11 reviews)
Paolo
£25
/h
1st lesson free!
Petar
4.9
4.9 (9 reviews)
Petar
£27
/h
1st lesson free!
Rajan
4.9
4.9 (11 reviews)
Rajan
£15
/h
1st lesson free!
Farooq
5
5 (13 reviews)
Farooq
£35
/h
1st lesson free!
Myriam
5
5 (15 reviews)
Myriam
£20
/h
1st lesson free!
Intasar
4.9
4.9 (23 reviews)
Intasar
£42
/h
1st lesson free!
Matthew
5
5 (17 reviews)
Matthew
£25
/h
1st lesson free!
Dr. Kritaphat
4.9
4.9 (6 reviews)
Dr. Kritaphat
£49
/h
1st lesson free!
Paolo
4.9
4.9 (11 reviews)
Paolo
£25
/h
1st lesson free!
Petar
4.9
4.9 (9 reviews)
Petar
£27
/h
1st lesson free!
Rajan
4.9
4.9 (11 reviews)
Rajan
£15
/h
1st lesson free!
Farooq
5
5 (13 reviews)
Farooq
£35
/h
1st lesson free!
Myriam
5
5 (15 reviews)
Myriam
£20
/h
First Lesson Free>

Example

Calculate this algorithm for all prime numbers less than 40.

1. First, write the numbers. In this case they will be between 2 and 40.

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

2. Remove the multiples of 2.

2 3 5 7
11 13 15 17 19
23 25 29
31 35 37

3. The next number in the list is 3. Since 3² < 40, eliminate the multiples of 3.

2 3 5 7
11 13 17 19
23 29
31 37

4. The next number in the list is 5. Since 5² < 40, eliminate the multiples of 5.

2 3 5 7
11 13 17 19
23 29
31 37

5. The next number in the list is 7. Since 7² > 40, the algorithm ends and the numbers that remain are prime.

2 3 5 7
11 13 17 19
23 29
31 37

Table of prime numbers

2 3 5 7 11 13 17 19
23 29 31 37
41 43 47 53 59
61 67 71 73 79
83 89 97
101 103 107 109 113
127 131 137 139
149 151 157
163 167 173 179
181 191 193 197 199
Need a Maths teacher?

Did you like the article?

1 Star2 Stars3 Stars4 Stars5 Stars 5.00/5 - 1 vote(s)
Loading...

Emma

I am passionate about travelling and currently live and work in Paris. I like to spend my time reading, gardening, running, learning languages and exploring new places.