Sieve of Sundaram
Here given code implementation process.
// 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 ]
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.
New Comment