Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Sieve of Sundaram
Summary
In mathematics, the sieve of Sundaram is a variant of the sieve of Eratosthenes, a simple deterministic algorithm for finding all the prime numbers up to a specified integer. It was discovered by Indian student S. P. Sundaram in 1934.
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 + 2.
The sieve of Sundaram sieves out the composite numbers just as the 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 .
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 is q = 2(i + j + 2ij) + 1. Then we have:
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.
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 2:
print(2, end=' ')
for i in range(1, k + 1):
if integers_list[i]:
print(2 * i + 1, end=' ')
The above obscure but as commonly implemented Python version of the Sieve of Sundaram hides the true complexity of the algorithm due to the following reasons:
The range for the outer i looping variable is much too large, resulting in redundant looping that can't perform any composite number representation culling; the proper range is to the array index represent odd numbers less than the square root of the range.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.