Sieve of Eratosthenes

The Sieve of Eratosthenes is a classic technique to identify prime numbers in a range of integers from 2 up to n.

How It Works

Start by listing all numbers from 2 to n.
Pick the first number (2).
Cross out every multiple of 2 in the list.
Move to the next remaining number (3).
Cross out all multiples of 3.
Repeat this process up to the square root of n, $ \sqrt{n} $.

When the algorithm finishes, only the prime numbers from 2 to n will be left on the list.

A Practical Example

Let's find the prime numbers up to 100.

First, list the numbers from 2 to 100 in a table.

	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
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Note: The number 1 is excluded because 1 is not considered a prime, as it lacks a unique factorization. For example, we can represent 1 in various ways as $$ 1 = 1^1=1^2=1^3 ... $$ A prime number, by definition, is divisible only by 1 and itself and has a unique factorization, no matter the order of factors.

To find the primes from 1 to 100, we only need to cross out the multiples of integers from 2 up to the square root of n=100, $ \sqrt{100}=10 $, so numbers from 2 to 10.

Start with 2 and cross out all its multiples.

	2	3	5	7	9
11		13	15	17	19
21		23	25	27	29
31		33	35	37	39
41		43	45	47	49
51		53	55	57	59
61		63	65	67	69
71		73	75	77	79
81		83	85	87	89
91		93	95	97	99

Then, select 3 and cross out all its remaining multiples.

	2	3	5	7
11		13		17	19
		23	25		29
31			35	37
41		43		47	49
		53	55		59
61			65	67
71		73		77	79
		83	85		89
91			95	97

Since 4 has already been crossed out, we know it’s not a prime number, so we can skip it.

Now move to 5, select it, and cross out all multiples of 5.

	2	3	5	7
11		13		17	19
		23			29
31				37
41		43		47	49
		53			59
61				67
71		73		77	79
		83			89
91				97

Finally, select 7 and cross out all its multiples.

	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

There are no more numbers less than 10 left to check, so the algorithm ends here.

The remaining numbers in the table are the prime numbers from 2 to 100.

And that’s how it works.

	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
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

	2	3	5	7	9
11		13	15	17	19
21		23	25	27	29
31		33	35	37	39
41		43	45	47	49
51		53	55	57	59
61		63	65	67	69
71		73	75	77	79
81		83	85	87	89
91		93	95	97	99

	2	3	5	7
11		13		17	19
		23	25		29
31			35	37
41		43		47	49
		53	55		59
61			65	67
71		73		77	79
		83	85		89
91			95	97

	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
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

	2	3	5	7	9
11		13	15	17	19
21		23	25	27	29
31		33	35	37	39
41		43	45	47	49
51		53	55	57	59
61		63	65	67	69
71		73	75	77	79
81		83	85	87	89
91		93	95	97	99

	2	3	5	7
11		13		17	19
		23	25		29
31			35	37
41		43		47	49
		53	55		59
61			65	67
71		73		77	79
		83	85		89
91			95	97

	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
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

	2	3	5	7	9
11		13	15	17	19
21		23	25	27	29
31		33	35	37	39
41		43	45	47	49
51		53	55	57	59
61		63	65	67	69
71		73	75	77	79
81		83	85	87	89
91		93	95	97	99

	2	3	5	7
11		13		17	19
		23	25		29
31			35	37
41		43		47	49
		53	55		59
61			65	67
71		73		77	79
		83	85		89
91			95	97