Sieve of Eratosthenes Find All Primes in DSA Java

Mental Model

We mark multiples of each number starting from 2 as not prime, so only primes remain unmarked.

Analogy: Imagine a list of numbers like a row of boxes. You paint over boxes that are multiples of smaller numbers, leaving only boxes with prime numbers unpainted.

Index:  0  1  2  3  4  5  6  7  8  9  10
Value:  F  F  T  T  T  T  T  T  T  T   T
       (F=not prime, T=prime candidate)

Dry Run Walkthrough

Input: Find all primes up to 10

Goal: Identify all prime numbers from 2 to 10 using the sieve method

Step 1: Initialize array with true for indices 2 to 10

Index:  0  1  2  3  4  5  6  7  8  9  10
Value:  F  F  T  T  T  T  T  T  T  T   T

Why: Start assuming all numbers from 2 are prime candidates

Step 2: Mark multiples of 2 (4,6,8,10) as not prime

Index:  0  1  2  3  4  5  6  7  8  9  10
Value:  F  F  T  T  F  T  F  T  F  T   F

Why: Multiples of 2 cannot be prime except 2 itself

Step 3: Move to next prime candidate 3, mark multiples (9) as not prime

Index:  0  1  2  3  4  5  6  7  8  9  10
Value:  F  F  T  T  F  T  F  T  F  F   F

Why: Multiples of 3 cannot be prime except 3 itself

Step 4: Next candidate 4 is marked false, skip it

Index:  0  1  2  3  4  5  6  7  8  9  10
Value:  F  F  T  T  F  T  F  T  F  F   F

Why: 4 is already marked not prime, so skip

Step 5: Next candidate 5 is true, no multiples ≤ 10 to mark

Index:  0  1  2  3  4  5  6  7  8  9  10
Value:  F  F  T  T  F  T  F  T  F  F   F

Why: No multiples of 5 less than or equal to 10 to mark

Step 6: Next candidate 6 is false, skip

Index:  0  1  2  3  4  5  6  7  8  9  10
Value:  F  F  T  T  F  T  F  T  F  F   F

Why: 6 is marked not prime, skip

Step 7: Next candidate 7 is true, no multiples ≤ 10 to mark

Index:  0  1  2  3  4  5  6  7  8  9  10
Value:  F  F  T  T  F  T  F  T  F  F   F

Why: No multiples of 7 less than or equal to 10 to mark

Result:

Primes are indices with true: 2, 3, 5, 7

Annotated Code

DSA Java

public class SieveOfEratosthenes {
    public static void findPrimes(int n) {
        boolean[] prime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            prime[i] = true; // assume all numbers from 2 to n are prime candidates
        }
        for (int p = 2; p * p <= n; p++) {
            if (prime[p]) {
                for (int i = p * p; i <= n; i += p) {
                    prime[i] = false; // mark multiples of p as not prime
                }
            }
        }
        for (int i = 2; i <= n; i++) {
            if (prime[i]) {
                System.out.print(i + " "); // print prime numbers
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        findPrimes(10); // example input
    }
}

prime[i] = true; // assume all numbers from 2 to n are prime candidates

initialize all numbers as potential primes

if (prime[p]) {

check if current number p is still marked prime

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

mark multiples of p starting from p squared as not prime

prime[i] = false; // mark multiples of p as not prime

exclude multiples of p from primes

if (prime[i]) {

print numbers still marked prime

Output

2 3 5 7 

Complexity Analysis

Time: O(n log log n) because we mark multiples of primes up to sqrt(n)

Space: O(n) because we use a boolean array of size n+1

vs Alternative: Compared to checking each number's divisibility individually (O(n sqrt n)), sieve is much faster for large n

Edge Cases

n less than 2

No primes found, no output

DSA Java

if (n < 2) return;

n equals 2

Only 2 is prime, printed correctly

DSA Java

for (int i = 2; i <= n; i++) { prime[i] = true; }

When to Use This Pattern

When asked to find all primes up to a number efficiently, use the Sieve of Eratosthenes because it marks multiples systematically to avoid repeated checks.

Common Mistakes

Mistake: Starting marking multiples from p instead of p squared
Fix: Start marking from p * p because smaller multiples were already marked by smaller primes

Mistake: Not limiting outer loop to p * p <= n
Fix: Stop outer loop at p * p <= n to avoid unnecessary checks

Summary

Finds all prime numbers up to a given limit by marking multiples as not prime.

Use when you need a fast way to list primes up to a number.

The key insight is to start marking multiples from the square of each prime.

Practice

1. What is the main purpose of the Sieve of Eratosthenes algorithm?

easy

A. To find all prime numbers up to a given limit

B. To sort an array of numbers

C. To find the greatest common divisor of two numbers

D. To reverse a string

Solution

1. Step 1: Understand the algorithm's goal

   The Sieve of Eratosthenes is designed to identify prime numbers efficiently.

2. Step 2: Recognize the output

   It marks multiples of primes as non-prime, leaving primes unmarked up to a limit.

3. Final Answer:

   To find all prime numbers up to a given limit -> Option A

4. Quick Check:

   Prime finding = To find all prime numbers up to a given limit [OK]

Hint: Sieve marks multiples to find primes fast [OK]

Common Mistakes:

• Confusing with sorting algorithms
• Thinking it finds divisors
• Assuming it manipulates strings

2. Which of the following Java code snippets correctly initializes the boolean array for the sieve to find primes up to n?

easy

A. boolean[] prime = new boolean[n+1]; Arrays.fill(prime, false);

B. boolean[] prime = new boolean[n+1]; Arrays.fill(prime, true);

C. boolean[] prime = new boolean[n]; Arrays.fill(prime, false);

D. boolean[] prime = new boolean[n]; Arrays.fill(prime, true);

Solution

1. Step 1: Check array size for indexing

   We need size n+1 to include number n as index.

2. Step 2: Initialize all as true

   All numbers start as prime candidates, so fill with true.

3. Final Answer:

   boolean[] prime = new boolean[n+1]; Arrays.fill(prime, true); -> Option B

4. Quick Check:

   Array size n+1 and true fill = boolean[] prime = new boolean[n+1]; Arrays.fill(prime, true); [OK]

Hint: Use n+1 size and fill true for sieve array [OK]

Common Mistakes:

• Using size n instead of n+1
• Filling array with false initially
• Confusing array size and indexing

3. What will be the output list of primes printed by the following Java code snippet for n = 10?

int n = 10;
boolean[] prime = new boolean[n+1];
Arrays.fill(prime, true);
prime[0] = false; prime[1] = false;
for (int p = 2; p * p <= n; p++) {
  if (prime[p]) {
    for (int i = p * p; i <= n; i += p) {
      prime[i] = false;
    }
  }
}
for (int i = 2; i <= n; i++) {
  if (prime[i]) System.out.print(i + " ");
}

medium

A. 2 3 5 7

B. 2 3 4 5 7

C. 1 2 3 5 7

D. 2 3 5 7 9

Solution

1. Step 1: Initialize primes and mark 0,1 false

   prime[0] and prime[1] are false; others true initially.

2. Step 2: Mark multiples of primes false

   Multiples of 2 (4,6,8,10) and 3 (9) are marked false.

3. Step 3: Print primes from 2 to 10

   Remaining true indices are 2,3,5,7.

4. Final Answer:

   2 3 5 7 -> Option A

5. Quick Check:

   Primes up to 10 = 2 3 5 7 [OK]

Hint: Mark multiples starting from p*p to optimize [OK]

Common Mistakes:

• Including 1 as prime
• Printing non-prime numbers like 4 or 9
• Not starting inner loop from p*p

4. Identify the error in the following Java code snippet implementing the Sieve of Eratosthenes:

int n = 20;
boolean[] prime = new boolean[n+1];
Arrays.fill(prime, true);
prime[0] = false; prime[1] = false;
for (int p = 2; p <= n; p++) {
  if (prime[p]) {
    for (int i = p * 2; i <= n; i += p) {
      prime[i] = false;
    }
  }
}

medium

A. Arrays.fill should initialize with false, not true

B. The inner loop should start from p, not p*2

C. The outer loop should run only up to sqrt(n), not n

D. prime[0] and prime[1] should be true

Solution

1. Step 1: Check outer loop range

   Outer loop runs from 2 to n, but it is enough to run up to sqrt(n) for efficiency.

2. Step 2: Confirm inner loop start and initialization

   Inner loop correctly starts at p*2; prime[0] and prime[1] are correctly false; array filled with true.

3. Final Answer:

   The outer loop should run only up to sqrt(n), not n -> Option C

4. Quick Check:

   Loop limit optimization = The outer loop should run only up to sqrt(n), not n [OK]

Hint: Outer loop limit is sqrt(n) for efficiency [OK]

Common Mistakes:

• Running outer loop up to n wastes time
• Starting inner loop incorrectly
• Wrong initialization of prime array

5. You want to find all prime numbers up to n = 50 using the Sieve of Eratosthenes. After running the sieve, how many prime numbers will be found?

hard

A. 13

B. 16

C. 14

D. 15

Solution

1. Step 1: List primes up to 50

   Primes are 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 (total 15).

2. Step 2: Count primes carefully

   Counting again: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 = 15 primes.

3. Step 3: Verify options

   15 says 15, 16 says 16; correct count is 15.

4. Final Answer:

   15 -> Option D

5. Quick Check:

   Count primes ≤ 50 = 15 [OK]

Hint: Memorize primes or count after sieve [OK]

Common Mistakes:

• Counting 1 as prime
• Miscounting primes between 40 and 50
• Assuming 16 primes instead of 15