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 ]
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