Sieve of Eratosthenes

Topic: 05. Maths (Primes)

1. Logical Breakdown

[x] Core Logic: Assume all prime.
[x] Process: Mark multiples of every prime starting from 2 as non-prime.

2. Visualization

graph TD Start["Array All True"] --> Loop["i from 2 to sqrt(N)"] Loop --> IsPrime["Is Prime?"] IsPrime -- Yes --> Mark["Mark Multiples False"] Mark --> Loop

3. Complexity

Time: O(N log log N)
Space: O(N)

4. Code

package com.dsa.maths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SieveOfEratosthenes {
    public List<Integer> solve(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;
    }
}