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.

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.

2345678910
11121314151617181920
21222324252627282930
31323334353637383940

2. Remove the multiples of 2.

2 357
1113151719
232529
313537

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

2 357
11131719
2329
3137

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

2 357
11131719
2329
3137

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

2 357
11131719
2329
3137

Table of prime numbers

235711131719
23293137
4143475359
6167717379
838997
101103107109113
127131137139
149151157
163167173179
181191193197199
Do you need to find a Maths tutor?

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.