Sieve of Sundaram
Introduction
The Sieve of Sundaram is a simple, deterministic algorithm for finding all prime numbers up to a specified integer. Named after its Indian originator, T. Sundaram, the algorithm operates by eliminating numbers of the form i + j + 2ij where i, j are nonnegative integers. The remaining numbers are doubled and incremented by one, giving all the odd prime numbers (and unity). The Sieve of Sundaram is simpler than the Sieve of Eratosthenes, and it does not generate any even primes.
Algorithm Description
The Sieve of Sundaram works by eliminating certain numbers from a list of 1 through n. It does this by crossing out numbers of the form i + j + 2ij where i, j are nonnegative integers. This is done for all values of i and j such that i + j + 2ij ≤ n. The remaining numbers are then doubled and incremented by one, yielding all the odd prime numbers (and unity). This algorithm does not generate even prime numbers.
The algorithm can be written in pseudocode as follows:
1. Create a list of numbers from 1 to n. Call this list A. 2. For each pair of numbers (i, j) such that i ≤ j and i + j + 2ij ≤ n, cross out the number i + j + 2ij from list A. 3. The remaining numbers in list A are the numbers of the form 2i + 1, where i is a number not crossed out in step 2. These are all the odd prime numbers (and unity).
Mathematical Background
The Sieve of Sundaram exploits the fact that any prime number (greater than 2) can be expressed as 2i + 1 for some integer i. By crossing out numbers of the form i + j + 2ij, the algorithm essentially marks the numbers that are not prime. The remaining numbers are then doubled and incremented by one, yielding all the odd prime numbers.
The reason this works is that any composite number can be expressed as a product of its factors. If a number of the form i + j + 2ij (which simplifies to (2i + 1)(2j + 1)) is crossed out, then the number 2i + 1 is not prime, because it has a factor of 2j + 1.
Comparison with Other Sieves
The Sieve of Sundaram is simpler than the Sieve of Eratosthenes, which is another popular algorithm for finding prime numbers. The Sieve of Eratosthenes works by crossing out multiples of each prime number, starting from 2. The Sieve of Sundaram, on the other hand, crosses out numbers based on their form i + j + 2ij, which is simpler to compute.
However, the Sieve of Sundaram does not generate even prime numbers, while the Sieve of Eratosthenes does. This is because the Sieve of Sundaram only generates numbers of the form 2i + 1, which are all odd. The only even prime number, 2, is not generated by the Sieve of Sundaram.
Computational Complexity
The time complexity of the Sieve of Sundaram is O(n log n), which is the same as the time complexity of the Sieve of Eratosthenes. However, the Sieve of Sundaram has a space complexity of O(n), while the Sieve of Eratosthenes has a space complexity of O(n log log n). This means that the Sieve of Sundaram requires more memory to run, which can be a disadvantage for large inputs.
Applications
The Sieve of Sundaram is primarily used for generating prime numbers. Prime numbers have several applications in computer science, particularly in cryptography. For example, the RSA encryption algorithm relies on the use of large prime numbers.