Sieve of Sundaram

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

Algorithm

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:

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 + 1.

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 , Sundaram's method crosses out for .

Correctness

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

Let q be an odd integer of the form . Then, q is excluded if and only if k is of the form , that is . Then we have:

So, an odd integer is excluded from the final list if and only if it has a factorization of the form — 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 .

def sieve_of_Sundaram(n):
    """The sieve of Sundaram is a simple deterministic algorithm for finding all the prime numbers up to a specified integer."""
    k = (n - 2) // 2
    integers_list = [True] * (k + 1)
    for i in range(1, k + 1):
        j = i
        while i + j + 2 * i * j <= k:
            integers_list[i + j + 2 * i * j] = False
            j += 1
    if n > 2:
        print(2, end=' ')
    for i in range(1, k + 1):
        if integers_list[i]:
            print(2 * i + 1, end=' ')

See also

References

  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.