Skip to main content

Bitwise Sieve

Here given code implementation process.

// C Program
// Print Prime numbers using
// Bitwise Sieve
#include <stdio.h>

int non_prime(int num, int position)
{
	return (num & (1 << position));
}
int update_status(int num, int position)
{
	return (num | (1 << position));
}
//Find all prime numbers which have smaller and equal to given number n
void bitwise_sieve(int n)
{
	if (n <= 1)
	{
		//When n are invalid to prime number 
		return;
	}
	int space = (n >> 5) + 2;
	//This are used to detect prime numbers
	int sieve[space];
	// Loop controlling variables
	int i = 0;
	int j = 0;
	//define some auxiliary variable
	int slot = 0;
	int position = 0;
	for (i = 3; i * i <= n; i = i + 2)
	{
		//get slot and position
		slot = i >> 5;
		position = i & 31;
		if (non_prime(sieve[slot], position) == 0)
		{
			for (j = i * i; j <= n; j += (i << 1))
			{
				//get slot and position
				slot = j >> 5;
				position = j & 31;
				sieve[slot] = update_status(sieve[slot], position);
			}
		}
	}
	printf("\n Prime of (2 - %d) are \n", n);
	//Display first element
	printf(" [ 2");
	for (i = 3; i <= n; i = i + 2)
	{
		//get slot and position
		slot = i >> 5;
		position = i & 31;
		if (non_prime(sieve[slot], position) == 0)
		{
			//When [i] is a prime number
			printf("  %d", i);
		}
	}
	printf(" ] \n");
}
int main()
{
	bitwise_sieve(25);
	bitwise_sieve(101);
	bitwise_sieve(200);
	return 0;
}

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 2  3  11  13  17  19  23  25  29  31  35  37  41  43  47  49  53  55  59  61  67  77  79  83  85  89  91  95  97  101 ]

 Prime of (2 - 200) are
 [ 2  3  11  13  17  19  23  25  29  31  35  37  41  43  47  49  53  55  59  61  67  77  79  83  85  89  91  95  97  101  103  107  109  113  115  119  125  127  131  139  145  151  157  163  175  181 ]
// Java Program
// Print prime number by using
// Bitwise Sieve
class BitwiseSieve
{
	public int non_prime(int num, int position)
	{
		return (num & (1 << position));
	}
	public int update_status(int num, int position)
	{
		return (num | (1 << position));
	}
	//Find all prime numbers which have smaller and equal to given number n
	public void bitwise_sieve(int n)
	{
		if (n <= 1)
		{
			//When n are invalid to prime number 
			return;
		}
		int space = (n >> 5) + 2;
		//This are used to detect prime numbers
		int[] sieve = new int[space];
		// Loop controlling variables
		int i = 0;
		int j = 0;
		//define some auxiliary variable
		int slot = 0;
		int position = 0;
		for (i = 3; i * i <= n; i = i + 2)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (non_prime(sieve[slot], position) == 0)
			{
				for (j = i * i; j <= n; j += (i << 1))
				{
					//get slot and position
					slot = j >> 5;
					position = j & 31;
					sieve[slot] = update_status(sieve[slot], position);
				}
			}
		}
		System.out.print("\n Prime of (2 - " + n + ") are \n");
		//Display first element
		System.out.print(" [ 2");
		for (i = 3; i <= n; i = i + 2)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (non_prime(sieve[slot], position) == 0)
			{
				//When [i] is a prime number
				System.out.print("  " + i);
			}
		}
		System.out.print(" ] \n");
	}
	public static void main(String[] args)
	{
		BitwiseSieve obj = new BitwiseSieve();
		//Test Case
		obj.bitwise_sieve(25);
		obj.bitwise_sieve(101);
		obj.bitwise_sieve(200);
	}
}

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 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 ]

 Prime of (2 - 200) are
 [ 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
// Bitwise Sieve

class BitwiseSieve
{
	public: 
    int non_prime(int num, int position)
	{
		return (num & (1 << position));
	}
	int update_status(int num, int position)
	{
		return (num | (1 << position));
	}
	//Find all prime numbers which have smaller and equal to given number n
	void bitwise_sieve(int n)
	{
		if (n <= 1)
		{
			//When n are invalid to prime number 
			return;
		}
		int space = (n >> 5) + 2;
		//This are used to detect prime numbers
		int sieve[space];
		// Loop controlling variables
		int i = 0;
		int j = 0;
		//define some auxiliary variable
		int slot = 0;
		int position = 0;
		for (i = 3; i *i <= n; i = i + 2)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (this->non_prime(sieve[slot], position) == 0)
			{
				for (j = i *i; j <= n; j += (i << 1))
				{
					//get slot and position
					slot = j >> 5;
					position = j & 31;
					sieve[slot] = this->update_status(sieve[slot], position);
				}
			}
		}
		cout << "\n Prime of (2 - " << n << ") are \n";
		//Display first element
		cout << " [ 2";
		for (i = 3; i <= n; i = i + 2)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (this->non_prime(sieve[slot], position) == 0)
			{
				//When [i] is a prime number
				cout << "  " << i;
			}
		}
		cout << " ] \n";
	}
};
int main()
{
	BitwiseSieve obj = BitwiseSieve();
	//Test Case
	obj.bitwise_sieve(25);
	obj.bitwise_sieve(101);
	obj.bitwise_sieve(200);
	return 0;
}

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 2  3  7  11  13  23  29  47  53  55  59  61  67  71  79  83  85  89  95  97  101 ]

 Prime of (2 - 200) are
 [ 2  3  7  11  13  23  29  47  53  55  59  61  67  71  79  83  85  89  95  97  101  103  107  109  113  115  125  127  131  139  151  157  181  199 ]
//Include namespace system
using System;

// C# Program
// Print prime number by using
// Bitwise Sieve

class BitwiseSieve
{
	public int non_prime(int num, int position)
	{
		return (num & (1 << position));
	}
	public int update_status(int num, int position)
	{
		return (num | (1 << position));
	}
	//Find all prime numbers which have smaller and equal to given number n
	public void bitwise_sieve(int n)
	{
		if (n <= 1)
		{
			//When n are invalid to prime number 
			return;
		}
		int space = (n >> 5) + 2;
		//This are used to detect prime numbers
		int[] sieve = new int[space];
		// Loop controlling variables
		int i = 0;
		int j = 0;
		//define some auxiliary variable
		int slot = 0;
		int position = 0;
		for (i = 3; i * i <= n; i = i + 2)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (non_prime(sieve[slot], position) == 0)
			{
				for (j = i * i; j <= n; j += (i << 1))
				{
					//get slot and position
					slot = j >> 5;
					position = j & 31;
					sieve[slot] = update_status(sieve[slot], position);
				}
			}
		}
		Console.Write("\n Prime of (2 - " + n + ") are \n");
		//Display first element
		Console.Write(" [ 2");
		for (i = 3; i <= n; i = i + 2)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (non_prime(sieve[slot], position) == 0)
			{
				//When [i] is a prime number
				Console.Write("  " + i);
			}
		}
		Console.Write(" ] \n");
	}
	public static void Main(String[] args)
	{
		BitwiseSieve obj = new BitwiseSieve();
		//Test Case
		obj.bitwise_sieve(25);
		obj.bitwise_sieve(101);
		obj.bitwise_sieve(200);
	}
}

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 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 ]

 Prime of (2 - 200) are
 [ 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
// Bitwise Sieve

class BitwiseSieve
{
	public	function non_prime($num, $position)
	{
		return ($num & (1 << $position));
	}
	public	function update_status($num, $position)
	{
		return ($num | (1 << $position));
	}
	//Find all prime numbers which have smaller and equal to given number n
	public	function bitwise_sieve($n)
	{
		if ($n <= 1)
		{
			//When n are invalid to prime number 
			return;
		}
		$space = ($n >> 5) + 2;
		//This are used to detect prime numbers
		$sieve = array_fill(0, $space, 0);
		// Loop controlling variables
		$i = 0;
		$j = 0;
		//define some auxiliary variable
		$slot = 0;
		$position = 0;
		for ($i = 3; $i * $i <= $n; $i = $i + 2)
		{
			//get slot and position
			$slot = $i >> 5;
			$position = $i & 31;
			if ($this->non_prime($sieve[$slot], $position) == 0)
			{
				for ($j = $i * $i; $j <= $n; $j += ($i << 1))
				{
					//get slot and position
					$slot = $j >> 5;
					$position = $j & 31;
					$sieve[$slot] = $this->update_status($sieve[$slot], $position);
				}
			}
		}
		echo "\n Prime of (2 - ". $n .") are \n";
		//Display first element
		echo " [ 2";
		for ($i = 3; $i <= $n; $i = $i + 2)
		{
			//get slot and position
			$slot = $i >> 5;
			$position = $i & 31;
			if ($this->non_prime($sieve[$slot], $position) == 0)
			{
				//When [i] is a prime number
				echo "  ". $i;
			}
		}
		echo " ] \n";
	}
}

function main()
{
	$obj = new BitwiseSieve();
	//Test Case
	$obj->bitwise_sieve(25);
	$obj->bitwise_sieve(101);
	$obj->bitwise_sieve(200);
}
main();

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 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 ]

 Prime of (2 - 200) are
 [ 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
// Bitwise Sieve

class BitwiseSieve
{
	non_prime(num, position)
	{
		return (num & (1 << position));
	}
	update_status(num, position)
	{
		return (num | (1 << position));
	}
	//Find all prime numbers which have smaller and equal to given number n
	bitwise_sieve(n)
	{
		if (n <= 1)
		{
			//When n are invalid to prime number 
			return;
		}
		var space = (n >> 5) + 2;
		//This are used to detect prime numbers
		var sieve = Array(space).fill(0);
		// Loop controlling variables
		var i = 0;
		var j = 0;
		//define some auxiliary variable
		var slot = 0;
		var position = 0;
		for (i = 3; i * i <= n; i = i + 2)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (this.non_prime(sieve[slot], position) == 0)
			{
				for (j = i * i; j <= n; j += (i << 1))
				{
					//get slot and position
					slot = j >> 5;
					position = j & 31;
					sieve[slot] = this.update_status(sieve[slot], position);
				}
			}
		}
		process.stdout.write("\n Prime of (2 - " + n + ") are \n");
		//Display first element
		process.stdout.write(" [ 2");
		for (i = 3; i <= n; i = i + 2)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (this.non_prime(sieve[slot], position) == 0)
			{
				//When [i] is a prime number
				process.stdout.write("  " + i);
			}
		}
		process.stdout.write(" ] \n");
	}
}

function main()
{
	var obj = new BitwiseSieve();
	//Test Case
	obj.bitwise_sieve(25);
	obj.bitwise_sieve(101);
	obj.bitwise_sieve(200);
}
main();

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 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 ]

 Prime of (2 - 200) are
 [ 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
#  Bitwise Sieve

class BitwiseSieve :
	def non_prime(self, num, position) :
		return (num & (1 << position))
	
	def update_status(self, num, position) :
		return (num | (1 << position))
	
	# Find all prime numbers which have smaller and equal to given number n
	def bitwise_sieve(self, n) :
		if (n <= 1) :
			# When n are invalid to prime number 
			return
		
		space = (n >> 5) + 2
		# This are used to detect prime numbers
		sieve = [0] * space
		# define some auxiliary variable
		slot = 0
		position = 0
		#  Loop controlling variables
		i = 3
		j = 0
		while (i * i <= n) :
			# get slot and position
			slot = i >> 5
			position = i & 31
			if (self.non_prime(sieve[slot], position) == 0) :
				j = i * i
				while (j <= n) :
					# get slot and position
					slot = j >> 5
					position = j & 31
					sieve[slot] = self.update_status(sieve[slot], position)
					j += (i << 1)
				
			
			i = i + 2
		
		print("\n Prime of (2 - ", n ,") are \n", end = "")
		# Display first element
		print(" [ 2", end = "")
		i = 3
		while (i <= n) :
			# get slot and position
			slot = i >> 5
			position = i & 31
			if (self.non_prime(sieve[slot], position) == 0) :
				# When [i] is a prime number
				print("  ", i, end = "")
			
			i = i + 2
		
		print(" ] \n", end = "")
	

def main() :
	obj = BitwiseSieve()
	# Test Case
	obj.bitwise_sieve(25)
	obj.bitwise_sieve(101)
	obj.bitwise_sieve(200)

if __name__ == "__main__": main()

Output

 Prime of (2 -  25 ) are
 [ 2   3   5   7   11   13   17   19   23 ]

 Prime of (2 -  101 ) are
 [ 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 ]

 Prime of (2 -  200 ) are
 [ 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
#  Bitwise Sieve
class BitwiseSieve

	def non_prime(num, position)
		return (num & (1 << position))
	end
	def update_status(num, position)
	
		return (num | (1 << position))
	end
	# Find all prime numbers which have smaller and equal to given number n
	def bitwise_sieve(n)
	
		if (n <= 1)
			# When n are invalid to prime number 
			return
		end
		space = (n >> 5) + 2
		# This are used to detect prime numbers
		sieve = Array.new(space) {0}
		# define some auxiliary variable
		slot = 0
		position = 0
		#  Loop controlling variables
		i = 3
		j = 0
		while (i * i <= n)
		
			# get slot and position
			slot = i >> 5
			position = i & 31
			if (self.non_prime(sieve[slot], position) == 0)
			
				j = i * i
				while (j <= n)
				
					# get slot and position
					slot = j >> 5
					position = j & 31
					sieve[slot] = self.update_status(sieve[slot], position)
					j += (i << 1)
				end
			end
			i = i + 2
		end
		print("\n Prime of (2 - ", n ,") are \n")
		# Display first element
		print(" [ 2")
		i = 3
		while (i <= n)
		
			# get slot and position
			slot = i >> 5
			position = i & 31
			if (self.non_prime(sieve[slot], position) == 0)
			
				# When [i] is a prime number
				print("  ", i)
			end
			i = i + 2
		end
		print(" ] \n")
	end
end
def main()

	obj = BitwiseSieve.new()
	# Test Case
	obj.bitwise_sieve(25)
	obj.bitwise_sieve(101)
	obj.bitwise_sieve(200)
end
main()

Output

 Prime of (2 - 25) are 
 [ 2  3  5  7  11  13  17  19  23 ] 

 Prime of (2 - 101) are 
 [ 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 ] 

 Prime of (2 - 200) are 
 [ 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
// Bitwise Sieve
class BitwiseSieve
{
	def non_prime(num: Int, position: Int): Int = {
		return (num & (1 << position));
	}
	def update_status(num: Int, position: Int): Int = {
		return (num | (1 << position));
	}
	//Find all prime numbers which have smaller and equal to given number n
	def bitwise_sieve(n: Int): Unit = {
		if (n <= 1)
		{
			//When n are invalid to prime number 
			return;
		}
		var space: Int = (n >> 5) + 2;
		//This are used to detect prime numbers
		var sieve: Array[Int] = Array.fill[Int](space)(0);
		//define some auxiliary variable
		var slot: Int = 0;
		var position: Int = 0;
		// Loop controlling variables
		var i: Int = 3;
		var j: Int = 0;
		while (i * i <= n)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (non_prime(sieve(slot), position) == 0)
			{
				j = i * i;
				while (j <= n)
				{
					//get slot and position
					slot = j >> 5;
					position = j & 31;
					sieve(slot) = update_status(sieve(slot), position);
					j += (i << 1);
				}
			}
			i = i + 2;
		}
		print("\n Prime of (2 - " + n + ") are \n");
		//Display first element
		print(" [ 2");
		i = 3;
		while (i <= n)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (non_prime(sieve(slot), position) == 0)
			{
				//When [i] is a prime number
				print("  " + i);
			}
			i = i + 2;
		}
		print(" ] \n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: BitwiseSieve = new BitwiseSieve();
		//Test Case
		obj.bitwise_sieve(25);
		obj.bitwise_sieve(101);
		obj.bitwise_sieve(200);
	}
}

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 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 ]

 Prime of (2 - 200) are
 [ 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
// Bitwise Sieve
class BitwiseSieve
{
	func non_prime(_ num: Int, _ position: Int) -> Int
	{
		return (num & (1 << position));
	}
	func update_status(_ num: Int, _ position: Int) -> Int
	{
		return (num | (1 << position));
	}
	//Find all prime numbers which have smaller and equal to given number n
	func bitwise_sieve(_ n: Int)
	{
		if (n <= 1)
		{
			//When n are invalid to prime number 
			return;
		}
		let space: Int = (n >> 5) + 2;
		//This are used to detect prime numbers
		var sieve: [Int] = Array(repeating: 0, count: space);
		//define some auxiliary variable
		var slot: Int = 0;
		var position: Int = 0;
		// Loop controlling variables
		var i: Int = 3;
		var j: Int = 0;
		while (i * i <= n)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (self.non_prime(sieve[slot], position) == 0)
			{
				j = i * i;
				while (j <= n)
				{
					//get slot and position
					slot = j >> 5;
					position = j & 31;
					sieve[slot] = self.update_status(sieve[slot], position);
					j += (i << 1);
				}
			}
			i = i + 2;
		}
		print("\n Prime of (2 - ", n ,") are \n", terminator: "");
		//Display first element
		print(" [ 2", terminator: "");
		i = 3;
		while (i <= n)
		{
			//get slot and position
			slot = i >> 5;
			position = i & 31;
			if (self.non_prime(sieve[slot], position) == 0)
			{
				//When [i] is a prime number
				print("  ", i, terminator: "");
			}
			i = i + 2;
		}
		print(" ] \n", terminator: "");
	}
}
func main()
{
	let obj: BitwiseSieve = BitwiseSieve();
	//Test Case
	obj.bitwise_sieve(25);
	obj.bitwise_sieve(101);
	obj.bitwise_sieve(200);
}
main();

Output

 Prime of (2 -  25 ) are
 [ 2   3   5   7   11   13   17   19   23 ]

 Prime of (2 -  101 ) are
 [ 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 ]

 Prime of (2 -  200 ) are
 [ 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