Sundaram's sieve is an algorithm for finding all odd primes up to a given
bound. Start with the integers from 1 to and cross out every number of the form
for positive integers
. For each remaining number
, output
. This gives all odd primes through
. Include 2 separately to obtain
all primes through that bound (Havil 2009).
The sieve works because
Every crossed-out number therefore corresponds to an odd composite number. Conversely, each odd composite number is a product
of two odd factors greater
than 1, which can be written as and
with
.
For example, take . For
, cross out 4, 7, and 10. For
, cross out 12. For
, the smallest value possible is 24. The surviving
indices are 1, 2, 3, 5, 6, 8, 9, and 11, giving the odd primes 3, 5, 7, 11, 13, 17, 19, and 23.
The first few terms of the array read by antidiagonals are 4, 7, 7, 10, 12, 10, ... (OEIS
A159919).