Sieve of eratosthenes
Here given code implementation process.
// C Program
// Print prime number by using
// Sieve of eratosthenes
#include <stdio.h>
//Find all prime numbers which have smaller and equal to given number n
void sieve_of_eratosthenes(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//this are used to detect prime numbers
int prime[n + 1];
// Loop controlling variables
int i;
int j;
// Initial two numbers are not prime (0 and 1)
prime[0] = 0;
prime[1] = 0;
// Set the initial (2 to n element is prime)
for (i = 2; i <= n; ++i)
{
prime[i] = 1;
}
// Initial 0 and 1 are not prime
// We start to 2
for (i = 2; i * i <= n; ++i)
{
if (prime[i] == 1)
{
//When i is prime number
//Modify the prime status of all next multiplier of location i
for (j = i * i; j <= n; j += i)
{
prime[j] = 0;
}
}
}
printf("\n All prime of (2 - %d) is : \n [", n);
//Display prime element
for (i = 0; i <= n; ++i)
{
if (prime[i] == 1)
{
printf(" %d", i);
}
}
printf(" ]\n");
}
int main()
{
//Test Case
sieve_of_eratosthenes(25);
sieve_of_eratosthenes(100);
sieve_of_eratosthenes(200);
return 0;
}Output
All prime of (2 - 25) is :
[ 2 3 5 7 11 13 17 19 23 ]
All prime of (2 - 100) 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 of (2 - 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 eratosthenes
public class SieveOfEratosthenes
{
//Find all prime numbers which have smaller and equal to given number n
public void sieve_of_eratosthenes(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//this are used to detect prime numbers
boolean[] prime = new boolean[n + 1];
// Loop controlling variables
int i;
int j;
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Set the initial (2 to n element is prime)
for (i = 2; i <= n; ++i)
{
prime[i] = true;
}
// Initial 0 and 1 are not prime
// We start to 2
for (i = 2; i * i <= n; ++i)
{
if (prime[i] == true)
{
//When i is prime number
//Modify the prime status of all next multiplier of location i
for (j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
System.out.print("\n All prime of (2 - " + n + ") is : \n [");
//Display prime element
for (i = 0; i <= n; ++i)
{
if (prime[i] == true)
{
System.out.print(" " + i);
}
}
System.out.print(" ]\n");
}
public static void main(String[] args)
{
SieveOfEratosthenes obj = new SieveOfEratosthenes();
//Test Case
obj.sieve_of_eratosthenes(25);
obj.sieve_of_eratosthenes(100);
obj.sieve_of_eratosthenes(200);
}
}Output
All prime of (2 - 25) is :
[ 2 3 5 7 11 13 17 19 23 ]
All prime of (2 - 100) 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 of (2 - 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 eratosthenes
class SieveOfEratosthenes
{
public:
//Find all prime numbers which have smaller and equal to given number n
void sieve_of_eratosthenes(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//this are used to detect prime numbers
bool prime[n + 1];
// Loop controlling variables
int i;
int j;
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Set the initial (2 to n element is prime)
for (i = 2; i <= n; ++i)
{
prime[i] = true;
}
// Initial 0 and 1 are not prime
// We start to 2
for (i = 2; i *i <= n; ++i)
{
if (prime[i] == true)
{
//When i is prime number
//Modify the prime status of all next multiplier of location i
for (j = i *i; j <= n; j += i)
{
prime[j] = false;
}
}
}
cout << "\n All prime of (2 - " << n << ") is : \n [";
//Display prime element
for (i = 0; i <= n; ++i)
{
if (prime[i] == true)
{
cout << " " << i;
}
}
cout << " ]\n";
}
};
int main()
{
SieveOfEratosthenes obj = SieveOfEratosthenes();
//Test Case
obj.sieve_of_eratosthenes(25);
obj.sieve_of_eratosthenes(100);
obj.sieve_of_eratosthenes(200);
return 0;
}Output
All prime of (2 - 25) is :
[ 2 3 5 7 11 13 17 19 23 ]
All prime of (2 - 100) 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 of (2 - 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 eratosthenes
public class SieveOfEratosthenes
{
//Find all prime numbers which have smaller and equal to given number n
public void sieve_of_eratosthenes(int n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
//this are used to detect prime numbers
Boolean[] prime = new Boolean[n + 1];
// Loop controlling variables
int i;
int j;
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Set the initial (2 to n element is prime)
for (i = 2; i <= n; ++i)
{
prime[i] = true;
}
// Initial 0 and 1 are not prime
// We start to 2
for (i = 2; i * i <= n; ++i)
{
if (prime[i] == true)
{
//When i is prime number
//Modify the prime status of all next multiplier of location i
for (j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
Console.Write("\n All prime of (2 - " + n + ") is : \n [");
//Display prime element
for (i = 0; i <= n; ++i)
{
if (prime[i] == true)
{
Console.Write(" " + i);
}
}
Console.Write(" ]\n");
}
public static void Main(String[] args)
{
SieveOfEratosthenes obj = new SieveOfEratosthenes();
//Test Case
obj.sieve_of_eratosthenes(25);
obj.sieve_of_eratosthenes(100);
obj.sieve_of_eratosthenes(200);
}
}Output
All prime of (2 - 25) is :
[ 2 3 5 7 11 13 17 19 23 ]
All prime of (2 - 100) 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 of (2 - 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 eratosthenes
class SieveOfEratosthenes
{
//Find all prime numbers which have smaller and equal to given number n
public function sieve_of_eratosthenes($n)
{
if ($n <= 1)
{
//When n are invalid to prime number
return;
}
// This are used to detect prime numbers
// Set the n all numbers is prime
$prime = array_fill(0, $n + 1, true);
// Loop controlling variables
$i = 0;
$j = 0;
// Initial two numbers are not prime (0 and 1)
$prime[0] = false;
$prime[1] = false;
// Initial 0 and 1 are not prime
// We start to 2
for ($i = 2; $i * $i <= $n; ++$i)
{
if ($prime[$i] == true)
{
//When i is prime number
//Modify the prime status of all next multiplier of location i
for ($j = $i * $i; $j <= $n; $j += $i)
{
$prime[$j] = false;
}
}
}
echo "\n All prime of (2 - ". $n .") is : \n [";
//Display prime element
for ($i = 0; $i <= $n; ++$i)
{
if ($prime[$i] == true)
{
echo " ". $i;
}
}
echo " ]\n";
}
}
function main()
{
$obj = new SieveOfEratosthenes();
//Test Case
$obj->sieve_of_eratosthenes(25);
$obj->sieve_of_eratosthenes(100);
$obj->sieve_of_eratosthenes(200);
}
main();Output
All prime of (2 - 25) is :
[ 2 3 5 7 11 13 17 19 23 ]
All prime of (2 - 100) 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 of (2 - 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 eratosthenes
class SieveOfEratosthenes
{
//Find all prime numbers which have smaller and equal to given number n
sieve_of_eratosthenes(n)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
// This are used to detect prime numbers
// Set the n all numbers is prime
var prime = Array(n + 1).fill(true);
// Loop controlling variables
var i = 0;
var j = 0;
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Initial 0 and 1 are not prime
// We start to 2
for (i = 2; i * i <= n; ++i)
{
if (prime[i] == true)
{
//When i is prime number
//Modify the prime status of all next multiplier of location i
for (j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
process.stdout.write("\n All prime of (2 - " + n + ") is : \n [");
//Display prime element
for (i = 0; i <= n; ++i)
{
if (prime[i] == true)
{
process.stdout.write(" " + i);
}
}
process.stdout.write(" ]\n");
}
}
function main()
{
var obj = new SieveOfEratosthenes();
//Test Case
obj.sieve_of_eratosthenes(25);
obj.sieve_of_eratosthenes(100);
obj.sieve_of_eratosthenes(200);
}
main();Output
All prime of (2 - 25) is :
[ 2 3 5 7 11 13 17 19 23 ]
All prime of (2 - 100) 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 of (2 - 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 eratosthenes
class SieveOfEratosthenes :
# Find all prime numbers which have smaller and equal to given number n
def sieve_of_eratosthenes(self, n) :
if (n <= 1) :
# When n are invalid to prime number
return
# This are used to detect prime numbers
# Set the n all numbers is prime
prime = [True] * (n + 1)
# Loop controlling variables
i = 0
j = 0
# Initial two numbers are not prime (0 and 1)
prime[0] = False
prime[1] = False
# We start to 2
i = 2
while (i * i <= n) :
if (prime[i] == True) :
# When i is prime number
# Modify the prime status of all next multiplier of location i
j = i * i
while (j <= n) :
prime[j] = False
j += i
i += 1
print("\n All prime of (2 - ", n ,") is : \n [", end = "")
# Display prime element
i = 0
while (i <= n) :
if (prime[i] == True) :
print(" ", i, end = "")
i += 1
print(" ]\n", end = "")
def main() :
obj = SieveOfEratosthenes()
# Test Case
obj.sieve_of_eratosthenes(25)
obj.sieve_of_eratosthenes(100)
obj.sieve_of_eratosthenes(200)
if __name__ == "__main__": main()Output
All prime of (2 - 25 ) is :
[ 2 3 5 7 11 13 17 19 23 ]
All prime of (2 - 100 ) 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 of (2 - 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 eratosthenes
class SieveOfEratosthenes
# Find all prime numbers which have smaller and equal to given number n
def sieve_of_eratosthenes(n)
if (n <= 1)
# When n are invalid to prime number
return
end
# This are used to detect prime numbers
# Set the n all numbers is prime
prime = Array.new(n + 1) {true}
# Loop controlling variables
i = 0
j = 0
# Initial two numbers are not prime (0 and 1)
prime[0] = false
prime[1] = false
# We start to 2
i = 2
while (i * i <= n)
if (prime[i] == true)
# When i is prime number
# Modify the prime status of all next multiplier of location i
j = i * i
while (j <= n)
prime[j] = false
j += i
end
end
i += 1
end
print("\n All prime of (2 - ", n ,") is : \n [")
# Display prime element
i = 0
while (i <= n)
if (prime[i] == true)
print(" ", i)
end
i += 1
end
print(" ]\n")
end
end
def main()
obj = SieveOfEratosthenes.new()
# Test Case
obj.sieve_of_eratosthenes(25)
obj.sieve_of_eratosthenes(100)
obj.sieve_of_eratosthenes(200)
end
main()Output
All prime of (2 - 25) is :
[ 2 3 5 7 11 13 17 19 23 ]
All prime of (2 - 100) 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 of (2 - 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 eratosthenes
class SieveOfEratosthenes
{
//Find all prime numbers which have smaller and equal to given number n
def sieve_of_eratosthenes(n: Int): Unit = {
if (n <= 1)
{
//When n are invalid to prime number
return;
}
// This are used to detect prime numbers
// Set the n all numbers is prime
var prime: Array[Boolean] = Array.fill[Boolean](n + 1)(true);
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
// Initial two numbers are not prime (0 and 1)
prime(0) = false;
prime(1) = false;
// We start to 2
i = 2;
while (i * i <= n)
{
if (prime(i) == true)
{
//When i is prime number
//Modify the prime status of all next multiplier of location i
j = i * i;
while (j <= n)
{
prime(j) = false;
j += i;
}
}
i += 1;
}
print("\n All prime of (2 - " + n + ") is : \n [");
//Display prime element
i = 0;
while (i <= n)
{
if (prime(i) == true)
{
print(" " + i);
}
i += 1;
}
print(" ]\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: SieveOfEratosthenes = new SieveOfEratosthenes();
//Test Case
obj.sieve_of_eratosthenes(25);
obj.sieve_of_eratosthenes(100);
obj.sieve_of_eratosthenes(200);
}
}Output
All prime of (2 - 25) is :
[ 2 3 5 7 11 13 17 19 23 ]
All prime of (2 - 100) 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 of (2 - 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 eratosthenes
class SieveOfEratosthenes
{
//Find all prime numbers which have smaller and equal to given number n
func sieve_of_eratosthenes(_ n: Int)
{
if (n <= 1)
{
//When n are invalid to prime number
return;
}
// This are used to detect prime numbers
// Set the n all numbers is prime
var prime: [Bool] = Array(repeating: true, count: n + 1);
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// We start to 2
i = 2;
while (i * i <= n)
{
if (prime[i] == true)
{
//When i is prime number
//Modify the prime status of all next multiplier of location i
j = i * i;
while (j <= n)
{
prime[j] = false;
j += i;
}
}
i += 1;
}
print("\n All prime of (2 - ", n ,") is : \n [", terminator: "");
//Display prime element
i = 0;
while (i <= n)
{
if (prime[i] == true)
{
print(" ", i, terminator: "");
}
i += 1;
}
print(" ]\n", terminator: "");
}
}
func main()
{
let obj: SieveOfEratosthenes = SieveOfEratosthenes();
//Test Case
obj.sieve_of_eratosthenes(25);
obj.sieve_of_eratosthenes(100);
obj.sieve_of_eratosthenes(200);
}
main();Output
All prime of (2 - 25 ) is :
[ 2 3 5 7 11 13 17 19 23 ]
All prime of (2 - 100 ) 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 of (2 - 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