Sieve of Sundaram

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, the sieve of Sundaram is a simple deterministic algorithm for finding all prime numbers up to a specified integer. It was discovered in 1934 by S. P. Sundaram, an Indian student from Sathyamangalam.[1][2]

Algorithm[edit]

Sieve of Sundaram: algorithm steps for primes below 202 (unoptimized).

Start with a list of the integers from 1 to n. From this list, remove all numbers of the form i + j + 2ij where:

  • i,j\in\mathbb{N},\ 1 \le i \le j
  • i + j + 2ij \le n

The remaining numbers are doubled and incremented by one, giving a list of the odd prime numbers (i.e., all primes except 2) below 2n + 2.

The sieve of Sundaram sieves out the composite numbers just as sieve of Eratosthenes does, but even numbers are not considered; the work of "crossing out" the multiples of 2 is done by the final double-and-increment step. Whenever Eratosthenes' method would cross out k different multiples of a prime 2i+1, Sundaram's method crosses out i + j(2i+1) for 1\le j\le \lfloor k/2\rfloor.

Correctness[edit]

If we start with integers from 1 to n, the final list contains only odd integers from 3 to 2n + 1. From this final list, some odd integers have been excluded: we must show these are precisely the composite odd integers less than 2n + 2.

Let q be an odd integer of the form 2k + 1. Then, q is excluded if and only if k is of the form i + j + 2ij, that's it q = 2(i + j + 2ij) + 1. Then we have:

q = 2(i + j + 2ij) + 1
= 2i + 2j + 4ij + 1
= (2i + 1)(2j + 1).

So, an odd integer is excluded from the final list if and only if it has a factorization of the form (2i + 1)(2j + 1) — which is to say, if it has a non-trivial odd factor. Therefore the list must be composed of exactly the set of odd prime numbers less than or equal to 2n + 2.

See also[edit]

References[edit]

  1. ^ V. Ramaswami Aiyar (1934). "Sundaram's Sieve for Prime Numbers". The Mathematics Student 2 (2): 73. ISSN 0025-5742. 
  2. ^ G. (1941). "Curiosa 81. A New Sieve for Prime Numbers". Scripta Mathematica 8 (3): 164. 

External links[edit]