Prime Numbers

A prime number has only two divisors: itself and one.

5, 13, 59.

The number 1 has only one divisor, so it 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 and a quotient less than or equal to the divisor is obtained, it is said that the number is prime.

Prime Numbers

So, 179 is a prime number.

Sieve of Eratosthenes

The sieve of Eratosthenes is an algorithm that allows one to find all the prime numbers less than a given natural number.

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.

  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 32 < 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 52 < 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 72 > 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