Sieve of Eratosthenes

In this post, we will see how to find prime numbers using the Sieve of Eratosthenes.

Prime numbers are natural numbers that have exactly two distinct factors: 1 and themselves. For example, 2, 3, 5, 7, 11, and 13 are prime numbers, but 4, 6, 8, 9, 10, and 12 are not. Finding prime numbers is an important problem in mathematics and computer science, as they have many applications in cryptography, number theory, and algorithms. The Sieve of Eratosthenes is a simple and elegant algorithm that can find all the prime numbers up to a given limit in a fast and efficient way.

Practice this problem

1. Overview and Working of Sieve of Eratosthenes

The Sieve of Eratosthenes algorithm works by iteratively marking as composite (not prime) the multiples of each prime number, starting from 2. The remaining unmarked numbers are primes. The algorithm can be visualized as follows:

Create a list of consecutive integers from 2 to n, where n is the upper limit.
Let p be the first unmarked number in the list, which is 2 initially.
Mark all the multiples of p from p^2 to n as composite. For example, if p is 2, mark 4, 6, 8, …, n as composite.
Find the next unmarked number in the list that is greater than p and assign it to p. If there is no such number, stop.
Repeat steps 3 and 4 until p^2 is greater than n.

2. Implementation of Sieve of Eratosthenes

One way to implement the Sieve of Eratosthenes is to use a boolean array to keep track of whether a number is marked or not. Here is a simple function that returns a list of all primes up to n using this method. For example, primes less than n = 50 are [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47].

C++

#include <iostream>

#include <vector>

#include <cmath>

#include <bitset>

using namespace std;

vector<int> sieveOfEratosthenes(int n) {

// Create a boolean array of size n+1

// Initially set all entries as true

// A value in prime[i] will be false if i is not a prime

bool prime[n+1];

for (int i = 0; i < n+1; i++) {

prime[i] = true;

}

// Start from the first prime number, which is 2

int p = 2;

// Loop until p^2 is greater than n

while (p * p <= n) {

// If p is a prime, mark all its multiples as composite

if (prime[p]) {

for (int i = p * p; i < n + 1; i += p) {

prime[i] = false;

}

// Find the next unmarked number greater than p

p++;

}

// Return the vector of primes

vector<int> primes;

for (int i = 2; i < n+1; i++) {

if (prime[i]) {

primes.push_back(i);

}

return primes;

}

int main() {

vector<int> primes = sieveOfEratosthenes(50);

for (int p : primes) {

cout << p << " ";

}

cout << endl;

return 0;

}

Java

import java.util.ArrayList;

import java.util.List;

class Main {

public static List<Integer> sieveOfEratosthenes(int n) {

// Create a boolean array of size n+1

// Initially set all entries as true

// A value in prime[i] will be false if i is not a prime

boolean[] prime = new boolean[n + 1];

for (int i = 0; i < n + 1; i++) {

prime[i] = true;

}

// Start from the first prime number, which is 2

int p = 2;

// Loop until p^2 is greater than n

while (p * p <= n) {

// If p is a prime, mark all its multiples as composite

if (prime[p]) {

for (int i = p * p; i < n + 1; i += p) {

prime[i] = false;

}

// Find the next unmarked number greater than p

p++;

}

// Return the list of primes

List<Integer> primes = new ArrayList<>();

for (int i = 2; i < n + 1; i++) {

if (prime[i]) {

primes.add(i);

}

return primes;

}

public static void main(String[] args) {

System.out.println(sieveOfEratosthenes(50));

}

Python

def sieve_of_eratosthenes(n):

# Create a boolean array of size n+1

# Initially set all entries as True

# A value in prime[i] will be False if i is not a prime

prime = [True for i in range(n + 1)]

# Start from the first prime number, which is 2

p = 2

# Loop until p^2 is greater than n

while p * p <= n:

# If p is a prime, mark all its multiples as composite

if prime[p]:

for i in range(p * p, n + 1, p):

prime[i] = False

# Find the next unmarked number greater than p

p += 1

# Return the list of primes

return [i for i in range(2, n + 1) if prime[i]]

print(sieve_of_eratosthenes(50))

3. Speed and Memory Optimizations for Sieve of Eratosthenes

The basic implementation of the Sieve of Eratosthenes can be improved in several ways to make it faster and more memory-efficient. Here are some common optimizations:

Start marking multiples from p^2 instead of p. This is because all the smaller multiples of p have already been marked by previous primes.
Use only odd numbers in the list. This is because all even numbers except for 2 are composite. This reduces the size of the array by half and also eliminates half of the iterations.
Use a bit array instead of a boolean array. This reduces the space complexity by a factor of 8, as each bit can store the value of one number instead of one byte.

Here is a modified function that implements these optimizations:

C++

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

vector<int> sieveOfEratosthenesOptimized(int n) {

// Create a bit array of size (n+1)/2

// Initially set all bits as 1

// A value in prime[i] will be 0 if 2*i+1 is not a prime

vector<int> prime((n+1)/2, 1);

// Start from the first odd prime number, which is 3

int p = 3;

// Loop until p^2 is greater than n

while (p * p <= n) {

// If p is a prime, mark all its odd multiples as composite

if (prime[p/2]) {

// The first odd multiple of p is p^2

// We increment by 2*p to get the next odd multiple

for (int i = p * p; i < n + 1; i += 2 * p) {

prime[i/2] = 0;

}

// Find the next odd unmarked number greater than p

p += 2;

}

// Return the vector of primes

vector<int> primes;

primes.push_back(2);

for (int i = 1; i < (n+1)/2; i++) {

if (prime[i]) {

primes.push_back(2*i+1);

}

return primes;

}

int main() {

vector<int> primes = sieveOfEratosthenesOptimized(50);

for (int p : primes) {

cout << p << " ";

}

cout << endl;

return 0;

}

Java

import java.util.ArrayList;

import java.util.List;

class Main {

public static List<Integer> sieveOfEratosthenesOptimized(int n) {

// Create a bit array of size (n+1)/2

// Initially set all bits as 1

// A value in prime[i] will be 0 if 2*i+1 is not a prime

byte[] prime = new byte[(n + 1) / 2];

for (int i = 0; i < (n + 1) / 2; i++) {

prime[i] = 1;

}

// Start from the first odd prime number, which is 3

int p = 3;

// Loop until p^2 is greater than n

while (p * p <= n) {

// If p is a prime, mark all its odd multiples as composite

if ((prime[p / 2] & 1) == 1) {

// The first odd multiple of p is p^2

// We increment by 2*p to get the next odd multiple

for (int i = p * p; i < n + 1; i += 2 * p) {

prime[i / 2] &= ~1;

}

// Find the next odd unmarked number greater than p

p += 2;

}

// Return the list of primes

List<Integer> primes = new ArrayList<>();

primes.add(2);

for (int i = 1; i < (n + 1) / 2; i++) {

if ((prime[i] & 1) == 1) {

primes.add(2 * i + 1);

}

return primes;

}

public static void main(String[] args) {

System.out.println(sieveOfEratosthenesOptimized(50));

}

Python

def sieve_of_eratosthenes_optimized(n):

# Create a bit array of size (n+1)//2

# Initially set all bits as 1

# A value in prime[i] will be 0 if 2*i+1 is not a prime

prime = [1 for i in range((n + 1) // 2)]

# Start from the first odd prime number, which is 3

p = 3

# Loop until p^2 is greater than n

while p * p <= n:

# If p is a prime, mark all its odd multiples as composite

if prime[p // 2]:

# The first odd multiple of p is p^2

# We increment by 2*p to get the next odd multiple

for i in range(p * p, n + 1, 2 * p):

prime[i // 2] = 0

# Find the next odd unmarked number greater than p

p += 2

# Return the list of primes

return [2] + [2 * i + 1 for i in range(1, (n + 1) // 2) if prime[i]]

print(sieve_of_eratosthenes_optimized(50))

1. Overview and Working of Sieve of Eratosthenes

2. Implementation of Sieve of Eratosthenes

C++

Java

Python

3. Speed and Memory Optimizations for Sieve of Eratosthenes

C++

Java

Python

Share this: