Sieve of Eratosthenes

Introduction

The Sieve of Eratosthenes is one of the oldest and most efficient algorithms to find all prime numbers up to a given number n. Designed more than 2200 years ago, it is still widely used in modern computing—especially in competitive programming, cryptography, and number theory problems.

Note: A prime number is a number greater than 1 that has no positive divisors other than 1 and itself. Examples: 2, 3, 5, 7, 11, etc.

Algorithm

• Initialize an array isPrime[] from 0 to n, initially set to true(1).

• Start with the first prime, which is 2.

• Mark all multiples of 2 (except 2) as non-prime (false(0) in the array).

• Move to the next unmarked number, 3, and mark all its multiples.

• Repeat this process for numbers up to √n.

After this, all numbers which remain marked as true are prime numbers.

Note:

Why repeat only upto √n - Because any composite number n must have at least one factor less than or equal to √n. Beyond that, all multiples have already been marked by smaller primes.

Visualization

Let’s sieve up to n = 30.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

void sieve(int n) {
    // Step 1: Create a boolean array "isPrime[0..n]" and initialize all entries as true.
    // A value in isPrime[i] will finally be false if i is Not a prime, else true.
    vector<bool> isPrime(n + 1, true);

    // 0 and 1 are not prime numbers
    isPrime[0] = isPrime[1] = false;

    // Step 2: Start from the first prime number, which is 2
    for (int p = 2; p * p <= n; ++p) {
        if (isPrime[p]) {
            // Step 3: Mark all multiples of p starting from p*p as false (not prime)
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    // Step 4: Print all prime numbers
    cout << "Prime numbers up to " << n << " are:\n";
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) cout << i << " ";
    }
    cout << "\n";
}

int main() {
    int n;
    cout << "Enter the value of n: ";
    cin >> n;
    sieve(n);
    return 0;
}

Java Implementation

import java.util.*;

public class SieveOfEratosthenes {
    static void sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= n; i += p)
                    isPrime[i] = false;
            }
        }
    
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) System.out.print(i + " ");
        }
    }
    public static void main (String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the value of n: ");
        int n = sc.nextInt();
        sieve(n);
    }
}

Time Complexity Analysis

Let’s break it down step-by-step:

• For each prime p, the algorithm marks all multiples of p starting from p*p up to n.

• The total number of times numbers get marked (i.e., inner loop operations) is:

  ∑ (n / p) for 2 ≤ p ≤ √n

This sum approximates to:

n × (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...)

The harmonic series over primes converges to log(log(n)), so:

Total Time=O(nloglogn)

This is much better than checking each number up to n one by one (which would be O(n√n) for primality testing).

Space Complexity Analysis

• A boolean array of size n+1 is used:

  Space = O(n)

Optimizations

• Start from p * p: All smaller multiples of p were already marked by earlier primes.

• Mark only odd numbers (since all even numbers > 2 are not prime): Reduces memory and computation.

Segmented Sieve: The most useful Variation

What Is the Segmented Sieve?

The Segmented Sieve is a way to find prime numbers in a specific range [L, R] when R is large (up to 10^12)
but the width of the range (R - L) is small (up to 10^6).

The key idea is to first find all primes up to √R using the regular Sieve of Eratosthenes. Then, you use these primes to mark non-prime numbers in the range [L, R].

Steps of Segmented Sieve:

• Find Primes up to √R: You first find all primes up to the square root of R because these primes are enough to help mark non-primes in the range [L, R].

• Mark Multiples in the Range: Using the primes from Step 1, you mark all numbers in the range [L, R] that are multiples of these primes.

• Remaining Numbers are Primes: After marking the multiples, the numbers that are not marked are the primes.

C++ Code for Segmented Sieve

#include <bits/stdc++.h>
using namespace std;

// Function to find all primes up to sqrt(R) using regular sieve
vector<int> simpleSieve(int limit) {
    vector<bool> isPrime(limit + 1, true); // Mark all numbers as prime initially
    isPrime[0] = isPrime[1] = false;      // 0 and 1 are not prime
    vector<int> primes;

    // Sieve to mark non-primes
    for (int p = 2; p * p <= limit; ++p) {
        if (isPrime[p]) {
            for (int i = p * p; i <= limit; i += p) {
                isPrime[i] = false;
            }
        }
    }

    // Collect all primes
    for (int p = 2; p <= limit; ++p) {
        if (isPrime[p]) {
            primes.push_back(p);
        }
    }
    return primes;
}

// Function to find primes in the range [L, R] using Segmented Sieve
void segmentedSieve(int L, int R) {
    int limit = sqrt(R) + 1;  // Find primes up to sqrt(R)
    vector<int> primes = simpleSieve(limit);

    // Create a boolean array for the range [L, R] and mark all numbers as prime initially
    vector<bool> isPrime(R - L + 1, true);

    // Use the primes to mark multiples as non-prime
    for (int i = 0; i < primes.size(); ++i) {
        int p = primes[i];

        // Find the first number in the range [L, R] that is a multiple of p
        int start = max(p * p, (L + p - 1) / p * p);

        for (int j = start; j <= R; j += p) {
            isPrime[j - L] = false;  // Mark non-primes
        }
    }

    // Print primes in the range [L, R]
    for (int i = 0; i <= R - L; ++i) {
        if (isPrime[i]) {
            cout << L + i << " ";  // If the number is still prime, print it
        }
    }
    cout << endl;
}

int main() {
    int L, R;
    cout << "Enter the range [L, R]: ";
    cin >> L >> R;
    segmentedSieve(L, R);  // Find primes in the range [L, R]
    return 0;
}

Java Code for Segmented Sieve

import java.util.*;

public class SegmentedSieve {

    // Function to find all primes up to sqrt(R) using regular sieve
    static List<Integer> simpleSieve(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        Arrays.fill(isPrime, true);  // Mark all numbers as prime initially
        isPrime[0] = isPrime[1] = false;  // 0 and 1 are not prime
        List<Integer> primes = new ArrayList<>();

        // Sieve to mark non-primes
        for (int p = 2; p * p <= limit; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= limit; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        // Collect all primes
        for (int p = 2; p <= limit; p++) {
            if (isPrime[p]) {
                primes.add(p);
            }
        }
        return primes;
    }

    // Function to find primes in the range [L, R] using Segmented Sieve
    static void segmentedSieve(int L, int R) {
        int limit = (int) Math.sqrt(R) + 1;  // Find primes up to sqrt(R)
        List<Integer> primes = simpleSieve(limit);

        // Create a boolean array for the range [L, R] and mark all numbers as prime initially
        boolean[] isPrime = new boolean[R - L + 1];
        Arrays.fill(isPrime, true);

        // Use the primes to mark multiples as non-prime
        for (int p : primes) {
            // Find the first number in the range [L, R] that is a multiple of p
            int start = Math.max(p * p, (L + p - 1) / p * p);

            for (int j = start; j <= R; j += p) {
                isPrime[j - L] = false;  // Mark non-primes
            }
        }

        // Print primes in the range [L, R]
        for (int i = 0; i <= R - L; i++) {
            if (isPrime[i]) {
                System.out.print((L + i) + " ");  // If the number is still prime, print it
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the range [L, R]: ");
        int L = sc.nextInt();
        int R = sc.nextInt();
        segmentedSieve(L, R);  // Find primes in the range [L, R]
    }
}

Step-by-Step Breakdown:

1.Looping over the primes:

for (int i = 0; i < primes.size(); ++i) {
    int p = primes[i];

• We loop through each prime number p found up to √R.

2.Finding the first multiple of p in the range [L, R]:

int start = max(p * p, (L + p - 1) / p * p);

• For each prime p, we need to find the first multiple of p in the range [L, R].

Here's how we calculate this:

• p * p: This is the smallest number that is a multiple of p. We start from p * p because any number smaller than this is either already marked by smaller primes or does not need to be considered.

• (L + p - 1) / p * p: This is a formula to find the first multiple of p in the range [L, R]. Let’s break this down:

  • (L + p - 1) / p: This is essentially calculating how many multiples of p have occurred before L. Adding p - 1 ensures that we round up to the next multiple of p if L is not already a multiple of p.

  • Multiply this by p to get the actual first multiple of p in the range.

• max(p * p, (L + p - 1) / p * p): We use max() because we want to ensure that we either start from p * p or from the next multiple of p in the range [L, R], whichever is larger.

Example:

• Suppose L = 10, R = 30, and we are currently considering the prime p = 5.

• p * p = 25, but the first multiple of 5 in the range [10, 30] is 10. Using the formula (L + p - 1) / p * p:

  • (10 + 5 - 1) / 5 = 14 / 5 = 2 (integer division), so the first multiple of 5 in the range is 2 * 5 = 10.

3.Marking the multiples of p as non-prime:

for (int j = start; j <= R; j += p) {
    isPrime[j - L] = false;  // Mark non-primes
}

• Now that we know the first multiple of p in the range [L, R], we start from start and mark all multiples of p as non-prime.

• The loop for (int j = start; j <= R; j += p) goes through all multiples of p from start to R, marking them as non-prime.

• isPrime[j - L] = false: Here we mark isPrime[j - L] = false, because the array isPrime corresponds to the range [L, R]. We subtract L from j to adjust the index for the boolean array.

Why Use the Segmented Sieve?

• Memory Efficiency: Instead of calculating all primes up to R, you only calculate the primes for the range [L, R].

• Faster for Large R: When R is very large (say 10^6 or more), the Segmented Sieve saves you from wasting memory and time sieving numbers that are not in your range.

• Practical for Small Ranges: It's ideal when the difference between L and R is small, even if R is very large.

Applications of the Sieve

• Preprocessing for fast primality checks

• Generating smallest prime factors (SPF) for factorization

• Solving Euler's totient function, number of divisors, sum of divisors

• Competitive programming: Commonly used in problems from Codeforces, LeetCode, AtCoder

• Cryptographic algorithms like RSA

Did You Know?

• Eratosthenes of Cyrene(inventor of Sieve Algorithm), a Greek mathematician, geographer, and astronomer, measured the Earth’s circumference with astonishing accuracy using shadows.

• The algorithm is still used in modern CPUs for efficient prime number generation benchmarks.

• It’s often one of the first examples introduced to demonstrate the power of precomputation and optimization in algorithms.

For more amazing content, click here

Till then,

Happy Coding!!!