Skip to main content

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 ]
Last updated on by Kalkicode




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.

New Comment