Posted on by Kalkicode
Code Mathematics

# Sieve of Sundaram

The Sieve of Sundaram is an efficient algorithm for generating prime numbers up to a given limit. It is named after the Indian mathematician S. P. Sundaram. This algorithm is an enhancement over the Sieve of Eratosthenes and is particularly useful for generating a list of prime numbers within a specific range. In this article, we will discuss and explain the Sieve of Sundaram algorithm using a C program.

## Problem Statement

Given a positive integer 'n', the task is to find and print all prime numbers that are less than 'n' using the Sieve of Sundaram algorithm.

## Example

For instance, when 'n' is 25, the prime numbers up to 25 are 2, 3, 5, 7, 11, 13, 17, 19, and 23. Similarly, for 'n' as 101, the prime numbers are 2, 3, 5, 7, 11, 13, ..., 97.

## Idea to Solve

The Sieve of Sundaram algorithm works by generating a list of numbers that potentially contain prime numbers and then marking out numbers that are not prime.

## Pseudocode

``````function sieve_of_sundaram(n):
if n <= 1:
Return
limit = (n - 2) / 2 + 1
Create an array 'sieve' of size 'limit' and initialize all elements to 0
Loop for i = 1 to limit:
Loop for j = i to limit:
num = i + j + 2 * i * j
If num < limit:
Toggle sieve[num]
Print "All prime between (1 -", n, ") is :"
Print "[", prime elements marked as 0 in 'sieve', "]"

function main():
sieve_of_sundaram(25)
sieve_of_sundaram(101)
sieve_of_sundaram(200)``````

## Algorithm Explanation

1. The `sieve_of_sundaram` function takes one parameter: 'n'.
2. It checks if 'n' is less than or equal to 1 and, if so, returns without performing any calculations.
3. It calculates the limit value to determine the size of the 'sieve' array.
4. It initializes the 'sieve' array, which will be used to mark non-prime numbers.
5. It iterates through values of 'i' and 'j', calculating num based on the Sundaram algorithm's formula.
6. It toggles the value of sieve[num] based on its value and the conditions specified in the algorithm.
7. It prints the prime elements (marked as 0) within the range (1 - n).

## Code Solution

``````// C Program
// Print prime number by using
// Sieve of Sundaram
#include <stdio.h>

//Find all prime numbers which have smaller than n
void sieve_of_sundaram(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//Calculate the number of  prime of given n
int limit = ((n - 2) / 2) + 1;
//This are used to detect prime numbers
int sieve[limit];
// Loop controlling variables
int i = 0;
int j = 0;
//Set initial all the numbers are non prime
for (i = 0; i < limit; ++i)
{
sieve[i] = 0;
}
for (i = 1; i < limit; ++i)
{
for (j = i;
(i + j + 2 * i * j) < limit; ++j)
{
//(i + j + 2ij) are unset
sieve[(i + j + 2 * i * j)] = 1;
}
}
printf("\n  All prime between (1 - %d) is :  \n [", n);
if (n >= 2)
{
printf(" %d", 2);
}
//Display prime element
for (i = 1; i < limit; ++i)
{
if (sieve[i] == 0)
{
printf("  %d", (i * 2) + 1);
}
}
printf("  ]\n");
}
int main()
{
//Test Case
sieve_of_sundaram(25);
sieve_of_sundaram(101);
sieve_of_sundaram(200);
return 0;
}``````

#### Output

``````  All prime between (1 - 25) is :
[ 2  3  5  7  11  13  17  19  23  ]

All prime between (1 - 101) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  ]

All prime between (1 - 200) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  ]``````
``````// Java Program
// Print prime number by using
// Sieve of sundaram
class SieveOfSundaram
{
//Find all prime numbers which have smaller than n
public void sieve_of_sundaram(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//Calculate the number of  prime of given n
int limit = ((n - 2) / 2) + 1;
//This are used to detect prime numbers
boolean[] sieve = new boolean[limit];
// Loop controlling variables
int i = 0;
int j = 0;
//Set initial all the numbers are non prime
for (i = 0; i < limit; ++i)
{
sieve[i] = false;
}
for (i = 1; i < limit; ++i)
{
for (j = i;
(i + j + 2 * i * j) < limit; ++j)
{
//(i + j + 2ij) are unset
sieve[(i + j + 2 * i * j)] = true;
}
}
System.out.print("\n All prime between (1 - " + n + ") is : \n [");
if (n >= 2)
{
System.out.print(" " + 2);
}
//Display prime element
for (i = 1; i < limit; ++i)
{
if (sieve[i] == false)
{
System.out.print("  " + ((i * 2) + 1));
}
}
System.out.print(" ]\n");
}
public static void main(String[] args)
{
SieveOfSundaram obj = new SieveOfSundaram();
//Test Case
obj.sieve_of_sundaram(25);
obj.sieve_of_sundaram(101);
obj.sieve_of_sundaram(200);
}
}``````

#### Output

`````` All prime between (1 - 25) is :
[ 2  3  5  7  11  13  17  19  23 ]

All prime between (1 - 101) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97 ]

All prime between (1 - 200) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]``````
``````//Include header file
#include <iostream>
using namespace std;

// C++ Program
// Print prime number by using
// Sieve of sundaram

class SieveOfSundaram
{
public:
//Find all prime numbers which have smaller than n
void sieve_of_sundaram(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//Calculate the number of  prime of given n
int limit = ((n - 2) / 2) + 1;
//This are used to detect prime numbers
bool sieve[limit];
// Loop controlling variables
int i = 0;
int j = 0;
//Set initial all the numbers are non prime
for (i = 0; i < limit; ++i)
{
sieve[i] = false;
}
for (i = 1; i < limit; ++i)
{
for (j = i;
(i + j + 2 *i *j) < limit; ++j)
{
//(i + j + 2ij) are unset
sieve[(i + j + 2 *i *j)] = true;
}
}
cout << "\n All prime between (1 - " << n << ") is : \n [";
if (n >= 2)
{
cout << " " << 2;
}
//Display prime element
for (i = 1; i < limit; ++i)
{
if (sieve[i] == false)
{
cout << "  " << ((i *2) + 1);
}
}
cout << " ]\n";
}
};
int main()
{
SieveOfSundaram obj = SieveOfSundaram();
//Test Case
obj.sieve_of_sundaram(25);
obj.sieve_of_sundaram(101);
obj.sieve_of_sundaram(200);
return 0;
}``````

#### Output

`````` All prime between (1 - 25) is :
[ 2  3  5  7  11  13  17  19  23 ]

All prime between (1 - 101) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97 ]

All prime between (1 - 200) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]``````
``````//Include namespace system
using System;

// C# Program
// Print prime number by using
// Sieve of sundaram

class SieveOfSundaram
{
//Find all prime numbers which have smaller than n
public void sieve_of_sundaram(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//Calculate the number of  prime of given n
int limit = ((n - 2) / 2) + 1;
//This are used to detect prime numbers
Boolean[] sieve = new Boolean[limit];
// Loop controlling variables
int i = 0;
int j = 0;
//Set initial all the numbers are non prime
for (i = 0; i < limit; ++i)
{
sieve[i] = false;
}
for (i = 1; i < limit; ++i)
{
for (j = i;
(i + j + 2 * i * j) < limit; ++j)
{
//(i + j + 2ij) are unset
sieve[(i + j + 2 * i * j)] = true;
}
}
Console.Write("\n All prime between (1 - " + n + ") is : \n [");
if (n >= 2)
{
Console.Write(" " + 2);
}
//Display prime element
for (i = 1; i < limit; ++i)
{
if (sieve[i] == false)
{
Console.Write("  " + ((i * 2) + 1));
}
}
Console.Write(" ]\n");
}
public static void Main(String[] args)
{
SieveOfSundaram obj = new SieveOfSundaram();
//Test Case
obj.sieve_of_sundaram(25);
obj.sieve_of_sundaram(101);
obj.sieve_of_sundaram(200);
}
}``````

#### Output

`````` All prime between (1 - 25) is :
[ 2  3  5  7  11  13  17  19  23 ]

All prime between (1 - 101) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97 ]

All prime between (1 - 200) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]``````
``````<?php
// Php Program
// Print prime number by using
// Sieve of sundaram

class SieveOfSundaram
{
//Find all prime numbers which have smaller than n
public  function sieve_of_sundaram(\$n)
{
if (\$n <= 1)
{
//When n are invalid to prime number
return;
}
//Calculate the number of  prime of given n
\$limit = (intval((\$n - 2) / 2)) + 1;
//This are used to detect prime numbers
//Set initial all the numbers are non prime
\$sieve = array_fill(0, \$limit, false);
// Loop controlling variables
\$i = 0;
\$j = 0;
for (\$i = 1; \$i < \$limit; ++\$i)
{
for (\$j = \$i;
(\$i + \$j + 2 * \$i * \$j) < \$limit; ++\$j)
{
//(i + j + 2ij) are unset
\$sieve[(\$i + \$j + 2 * \$i * \$j)] = true;
}
}
echo "\n All prime between (1 - ". \$n .") is : \n [";
if (\$n >= 2)
{
echo " ". 2;
}
//Display prime element
for (\$i = 1; \$i < \$limit; ++\$i)
{
if (\$sieve[\$i] == false)
{
echo "  ". ((\$i * 2) + 1);
}
}
echo " ]\n";
}
}

function main()
{
\$obj = new SieveOfSundaram();
//Test Case
\$obj->sieve_of_sundaram(25);
\$obj->sieve_of_sundaram(101);
\$obj->sieve_of_sundaram(200);
}
main();``````

#### Output

`````` All prime between (1 - 25) is :
[ 2  3  5  7  11  13  17  19  23 ]

All prime between (1 - 101) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97 ]

All prime between (1 - 200) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]``````
``````// Node Js Program
// Print prime number by using
// Sieve of sundaram
class SieveOfSundaram
{
//Find all prime numbers which have smaller than n
sieve_of_sundaram(n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//Calculate the number of  prime of given n
var limit = (parseInt((n - 2) / 2)) + 1;
//This are used to detect prime numbers
//Set initial all the numbers are non prime
var sieve = Array(limit).fill(false);
// Loop controlling variables
var i = 0;
var j = 0;
for (i = 1; i < limit; ++i)
{
for (j = i;
(i + j + 2 * i * j) < limit; ++j)
{
//(i + j + 2ij) are unset
sieve[(i + j + 2 * i * j)] = true;
}
}
process.stdout.write("\n All prime between (1 - " + n + ") is : \n [");
if (n >= 2)
{
process.stdout.write(" " + 2);
}
//Display prime element
for (i = 1; i < limit; ++i)
{
if (sieve[i] == false)
{
process.stdout.write("  " + ((i * 2) + 1));
}
}
process.stdout.write(" ]\n");
}
}

function main()
{
var obj = new SieveOfSundaram();
//Test Case
obj.sieve_of_sundaram(25);
obj.sieve_of_sundaram(101);
obj.sieve_of_sundaram(200);
}
main();``````

#### Output

`````` All prime between (1 - 25) is :
[ 2  3  5  7  11  13  17  19  23 ]

All prime between (1 - 101) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97 ]

All prime between (1 - 200) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]``````
``````#  Python 3 Program
#  Print prime number by using
#  Sieve of sundaram

class SieveOfSundaram :
# Find all prime numbers which have smaller than n
def sieve_of_sundaram(self, n) :
if (n <= 1) :
# When n are invalid to prime number
return

# Calculate the number of  prime of given n
limit = (int((n - 2) / 2)) + 1
# This are used to detect prime numbers
# Set initial all the numbers are non prime
sieve = [False] * limit
#  Loop controlling variables
i = 1
j = 0
while (i < limit) :
j = i
while ((i + j + 2 * i * j) < limit) :
# (i + j + 2ij) are unset
sieve[(i + j + 2 * i * j)] = True
j += 1

i += 1

print("\n All prime between (1 - ", n ,") is : \n [", end = "")
if (n >= 2) :
print(" ", 2, end = "")

# Display prime element
i = 1
while (i < limit) :
if (sieve[i] == False) :
print("  ", ((i * 2) + 1), end = "")

i += 1

print(" ]\n", end = "")

def main() :
obj = SieveOfSundaram()
# Test Case
obj.sieve_of_sundaram(25)
obj.sieve_of_sundaram(101)
obj.sieve_of_sundaram(200)

if __name__ == "__main__": main()``````

#### Output

`````` All prime between (1 -  25 ) is :
[  2   3   5   7   11   13   17   19   23 ]

All prime between (1 -  101 ) is :
[  2   3   5   7   11   13   17   19   23   29   31   37   41   43   47   53   59   61   67   71   73   79   83   89   97 ]

All prime between (1 -  200 ) is :
[  2   3   5   7   11   13   17   19   23   29   31   37   41   43   47   53   59   61   67   71   73   79   83   89   97   101   103   107   109   113   127   131   137   139   149   151   157   163   167   173   179   181   191   193   197   199 ]``````
``````#  Ruby Program
#  Print prime number by using
#  Sieve of sundaram

class SieveOfSundaram

# Find all prime numbers which have smaller than n
def sieve_of_sundaram(n)

if (n <= 1)

# When n are invalid to prime number
return
end
# Calculate the number of  prime of given n
limit = ((n - 2) / 2) + 1
# This are used to detect prime numbers
# Set initial all the numbers are non prime
sieve = Array.new(limit) {false}
#  Loop controlling variables
i = 1
j = 0
while (i < limit)

j = i
while ((i + j + 2 * i * j) < limit)

# (i + j + 2ij) are unset
sieve[(i + j + 2 * i * j)] = true
j += 1
end
i += 1
end
print("\n All prime between (1 - ", n ,") is : \n [")
if (n >= 2)

print(" ", 2)
end
# Display prime element
i = 1
while (i < limit)

if (sieve[i] == false)

print("  ", ((i * 2) + 1))
end
i += 1
end
print(" ]\n")
end
end
def main()

obj = SieveOfSundaram.new()
# Test Case
obj.sieve_of_sundaram(25)
obj.sieve_of_sundaram(101)
obj.sieve_of_sundaram(200)
end
main()``````

#### Output

`````` All prime between (1 - 25) is :
[ 2  3  5  7  11  13  17  19  23 ]

All prime between (1 - 101) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97 ]

All prime between (1 - 200) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]
``````
``````// Scala Program
// Print prime number by using
// Sieve of sundaram

class SieveOfSundaram
{
//Find all prime numbers which have smaller than n
def sieve_of_sundaram(n: Int): Unit = {
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//Calculate the number of  prime of given n
var limit: Int = (((n - 2) / 2).toInt) + 1;
//This are used to detect prime numbers
//Set initial all the numbers are non prime
var sieve: Array[Boolean] = Array.fill[Boolean](limit)(false);
// Loop controlling variables
var i: Int = 1;
var j: Int = 0;
while (i < limit)
{
j = i;
while ((i + j + 2 * i * j) < limit)
{
//(i + j + 2ij) are unset
sieve((i + j + 2 * i * j)) = true;
j += 1;
}
i += 1;
}
print("\n All prime between (1 - " + n + ") is : \n [");
if (n >= 2)
{
print(" " + 2);
}
//Display prime element
i = 1;
while (i < limit)
{
if (sieve(i) == false)
{
print("  " + ((i * 2) + 1));
}
i += 1;
}
print(" ]\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: SieveOfSundaram = new SieveOfSundaram();
//Test Case
obj.sieve_of_sundaram(25);
obj.sieve_of_sundaram(101);
obj.sieve_of_sundaram(200);
}
}``````

#### Output

`````` All prime between (1 - 25) is :
[ 2  3  5  7  11  13  17  19  23 ]

All prime between (1 - 101) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97 ]

All prime between (1 - 200) is :
[ 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]``````
``````// Swift Program
// Print prime number by using
// Sieve of sundaram

class SieveOfSundaram
{
//Find all prime numbers which have smaller than n
func sieve_of_sundaram(_ n: Int)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//Calculate the number of  prime of given n
let limit: Int = ((n - 2) / 2) + 1;
//This are used to detect prime numbers
//Set initial all the numbers are non prime
var sieve: [Bool] = Array(repeating: false, count: limit);
// Loop controlling variables
var i: Int = 1;
var j: Int = 0;
while (i < limit)
{
j = i;
while ((i + j + 2 * i * j) < limit)
{
//(i + j + 2ij) are unset
sieve[(i + j + 2 * i * j)] = true;
j += 1;
}
i += 1;
}
print("\n All prime between (1 - ", n ,") is : \n [", terminator: "");
if (n >= 2)
{
print(" ", 2, terminator: "");
}
//Display prime element
i = 1;
while (i < limit)
{
if (sieve[i] == false)
{
print("  ", ((i * 2) + 1), terminator: "");
}
i += 1;
}
print(" ]\n", terminator: "");
}
}
func main()
{
let obj: SieveOfSundaram = SieveOfSundaram();
//Test Case
obj.sieve_of_sundaram(25);
obj.sieve_of_sundaram(101);
obj.sieve_of_sundaram(200);
}
main();``````

#### Output

`````` All prime between (1 -  25 ) is :
[  2   3   5   7   11   13   17   19   23 ]

All prime between (1 -  101 ) is :
[  2   3   5   7   11   13   17   19   23   29   31   37   41   43   47   53   59   61   67   71   73   79   83   89   97 ]

All prime between (1 -  200 ) is :
[  2   3   5   7   11   13   17   19   23   29   31   37   41   43   47   53   59   61   67   71   73   79   83   89   97   101   103   107   109   113   127   131   137   139   149   151   157   163   167   173   179   181   191   193   197   199 ]``````

## Time Complexity

The Sieve of Sundaram algorithm has a time complexity of approximately O(n * log n). While it's more efficient than trial division for generating prime numbers, other algorithms like the Sieve of Eratosthenes and Sieve of Atkin may have better performance.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post