AntInLoop

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]