Exercise 552Number theory › PrimesHigh schoolAdded 3 Nov 2026

The sieve of Eratosthenes

#sieve#Eratosthenes#primes

Statement

Use the sieve of Eratosthenes to list all primes less than $30$ .

Hint

Cross out multiples of each prime starting from $2$ , up to $\sqrt{30}\approx5.5$ .

Show solutionHide solution

Start. List $2,3,\ldots,29$ .

Cross out multiples of 2 (except $2$ ): $4,6,8,10,12,14,16,18,20,22,24,26,28$ .

Cross out multiples of 3 (except $3$ ): $9,15,21,27$ (some already removed).

Cross out multiples of 5 (except $5$ ): $25$ .

Remaining primes. $2,3,5,7,11,13,17,19,23,29$ .

Conclusion. Ten primes less than $30$ .