Sieve-of-eratosthenes

Problem link : Sieve-of-eratosthenes

Problem Statement

Given a positive integer n, return all prime numbers less than or equal to n using the Sieve of Eratosthenes algorithm.

A prime number is a number greater than 1 that is divisible only by 1 and itself.

Examples

Example 1:

• Input: n = 10

• Output: 2 3 5 7

• Explanation: These are all the prime numbers ≤ 10

Example 2:

• Input: n = 35

• Output: 2 3 5 7 11 13 17 19 23 29 31

• Explanation: These are the primes ≤ 35

Constraints

• 1 ≤ n ≤ 10⁴

Intuition

To check for primes individually up to n would require checking each number for divisibility — a time-consuming process.

Instead, the Sieve of Eratosthenes improves efficiency by:

1. Assuming all numbers from 2 to n are prime.

2. Iteratively marking the multiples of each prime as non-prime.

Approach

1. Create a boolean array isPrime[] of size n + 1, initialized to true.

2. Set isPrime[0] and isPrime[1] to false since 0 and 1 are not primes.

3. Iterate i from 2 to √n:

   • If isPrime[i] == true, mark all multiples of i (starting from i*i) as false.

4. After the loop, the indices in isPrime[] which remain true are the prime numbers.

Java Code

import java.util.*;

class Solution {
    static List<Integer> sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true); // Assume all are prime initially
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                // Mark all multiples of i as non-prime
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // Collect all primes
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }

        return primes;
    }
}

Dry Run

Input: n = 10

• Initial isPrime[] = [false, false, true, true, true, true, true, true, true, true, true]

Step 1: i = 2

• Mark 4, 6, 8, 10 as false

Step 2: i = 3

• Mark 9 as false

Resulting Primes: 2, 3, 5, 7

Time Complexity

• O(n log log n) — Efficient for generating primes up to n

• Inner loop runs fewer times as i increases

Space Complexity

• O(n) — Due to boolean array of size n + 1

Conclusion

The Sieve of Eratosthenes is an optimal algorithm to find all primes ≤ n.
Its time efficiency and simplicity make it a classic technique in number theory and competitive programming.