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		9		11		13		15		17		19
21		23		25		27		29		31		33		35		37		39

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		25				29		31				35		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

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

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

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