Sieve of Eratosthenes Find All Primes in DSA Java - Execution Trace

Concept Flow - Sieve of Eratosthenes Find All Primes

Start with list 2 to n

↓

Mark all multiples of current prime as not prime

↓

Move to next unmarked number

↓

Repeat until current prime^2 > n

↓

Collect all unmarked numbers as primes

Start with numbers from 2 to n, mark multiples of each prime as not prime, then collect remaining unmarked numbers as primes.

Execution Sample

DSA Java

int n = 10;
boolean[] isPrime = new boolean[n+1];
Arrays.fill(isPrime, true);
isPrime[0] = false; 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;
}

Marks non-prime numbers up to 10 using the sieve method.

Execution Table

Step	Operation	Current Prime (i)	Marking Multiples	Array State (index:prime?)	Notes
1	Initialize array	-	-	0:F, 1:F, 2:T, 3:T, 4:T, 5:T, 6:T, 7:T, 8:T, 9:T, 10:T	Set 0 and 1 as not prime, others true
2	Check i=2 (prime)	2	Mark multiples 4,6,8,10 as false	0:F,1:F,2:T,3:T,4:F,5:T,6:F,7:T,8:F,9:T,10:F	Multiples of 2 marked not prime
3	Check i=3 (prime)	3	Mark multiples 9 as false	0:F,1:F,2:T,3:T,4:F,5:T,6:F,7:T,8:F,9:F,10:F	Multiple 9 marked not prime
4	Check i=4 (not prime)	4	-	No change	Skip since 4 is marked not prime
5	Check i=5 (stop)	5	-	-	Stop since 5*5=25 > 10
6	Collect primes	-	-	2:T,3:T,5:T,7:T	Remaining true indices are primes

💡 Stop when current prime squared exceeds n (5*5=25 > 10)

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	-	2	3	4	5	-	-
isPrime[4]	true	false	false	false	false	false	false
isPrime[9]	true	true	false	false	false	false	false
Primes collected	-	-	-	-	-	-	[2, 3, 5, 7]

Key Moments - 3 Insights

Why do we start marking multiples from i*i instead of 2*i?

Because smaller multiples like 2*i, 3*i were already marked by smaller primes. See Step 2 where multiples start at 4 (2*2).

Why do we stop the outer loop when i*i > n?

Because any composite number less than or equal to n must have a factor less than or equal to sqrt(n). See Step 5 where loop stops at i=5 since 5*5=25 > 10.

Why are 0 and 1 marked as not prime at the start?

By definition, primes start from 2. So 0 and 1 are set false initially as shown in Step 1.

Visual Quiz - 3 Questions

Look at the execution table, what is the state of isPrime[6] after Step 2?

A true

B unchanged

C false

D not initialized

💡 Hint

Check Step 2 where multiples of 2 including 6 are marked false.

At which step does the algorithm stop checking new primes?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

See Step 5 where i=5 and 5*5 > 10, so loop stops.

If n was increased to 25, what would be the first multiple marked false when i=5?

A 10

B 25

C 15

D 20

💡 Hint

Multiples start from i*i, so for i=5, marking starts at 25.

Concept Snapshot

Sieve of Eratosthenes:
- Create boolean array from 0 to n
- Mark 0 and 1 as not prime
- For i from 2 to sqrt(n):
  - If i is prime, mark multiples i*i, i*i+i, ... as not prime
- Remaining true indices are primes
- Efficiently finds all primes up to n

Full Transcript

The Sieve of Eratosthenes finds all prime numbers up to a number n by marking multiples of each prime as not prime. We start with an array marking all numbers from 2 to n as true (potential primes). We then iterate from 2 up to the square root of n. For each number i that is still marked true, we mark all multiples of i starting from i squared as false. We stop when i squared exceeds n because all composites have smaller factors. Finally, the numbers still marked true are primes. This method efficiently eliminates non-primes and collects primes in O(n log log n) time.

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