Maths WorkshopMaths problems with full solutions
Exercise 1843Number theory › PrimesOlympiadAdded 3 Nov 2026

The sieve of Sundaram

#sieve#Sundaram#primes

Statement

Describe the sieve of Sundaram and generate primes up to 3030.

Hint

Write numbers nn not of the form 2ij+i+j2ij+i+j; then 2n+12n+1 are odd primes.

Show solutionHide solution

Solution

Sieve. For n=1,2,…,Nn=1,2,\ldots,N, remove numbers of the form 2ij+i+j2ij+i+j with i,j≥1i,j\ge1. The remaining nn give primes 2n+12n+1.

Compute up to 3030. N=14N=14 (so 2N+1=292N+1=29). Removed numbers: 2ij+i+j2ij+i+j: 4,7,10,12,13,16,17,19,22,24,25,27,28,31,…4,7,10,12,13,16,17,19,22,24,25,27,28,31,\ldots (within range 11–1414: 4,7,10,12,134,7,10,12,13). Remaining nn in 11–1414: 1,2,3,5,6,8,9,11,141,2,3,5,6,8,9,11,14. Primes: 2⋅1+1=32\cdot1+1=3, 55, 77, 1111, 1313, 1717, 1919, 2323, 2929.

Conclusion. Sieve gives odd primes up to 3030.