Sieve of Eratosthenes Code Implementations
Complete Sieve of Eratosthenes code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Sieve of Eratosthenes Guide ยท Launch Interactive Visualizer
C++ Implementation
// Sieve of Eratosthenes Implementation in C++
#include <vector>
class Sieve {
public:
static std::vector<int> sieveOfEratosthenes(int n) {
std::vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
std::vector<int> primes;
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) {
primes.push_back(i);
}
}
return primes;
}
};JAVA Implementation
// Sieve of Eratosthenes Implementation in Java
import java.util.*;
public class Sieve {
public static List<Integer> sieveOfEratosthenes(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.add(i);
}
}
return primes;
}
}JAVASCRIPT Implementation
// Sieve of Eratosthenes Implementation in JavaScript
function sieveOfEratosthenes(n) {
const isPrime = new Array(n + 1).fill(true);
isPrime[0] = isPrime[1] = false;
for (let i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (let j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
const primes = [];
for (let i = 2; i <= n; i++) {
if (isPrime[i]) primes.push(i);
}
return primes;
}PYTHON Implementation
# Sieve of Eratosthenes Implementation in Python
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0:2] = [False, False]
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i, prime in enumerate(is_prime) if prime]