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

Concept Flow - Sieve of Eratosthenes Find All Primes

Create array of size n+1, all true

↓

Set 0 and 1 as not prime

↓

Start from p=2

↓

Is p*p <= n?

No→Collect primes from array

Yes↓

Mark multiples of p as not prime

↓

Increment p by 1

↩Back to check p*p <= n

Start with all numbers marked prime, then repeatedly mark multiples of each prime as not prime until reaching the square root of n.

Execution Sample

DSA Javascript

function sieve(n) {
  const primes = Array(n+1).fill(true);
  primes[0] = primes[1] = false;
  for (let p = 2; p * p <= n; p++) {
    if (primes[p]) {
      for (let i = p * p; i <= n; i += p) primes[i] = false;
    }
  }
  return primes.map((v, i) => v ? i : null).filter(x => x !== null);
}

This code finds all prime numbers up to n using the sieve method by marking multiples as not prime.

Execution Table

Step	Operation	Current p	Marking Multiples	Array State (true=prime, false=not prime)	Visual State
1	Initialize array	-	-	[false, false, true, true, true, true, true, true, true, true]	Index: 0 1 2 3 4 5 6 7 8 9 Value: F F T T T T T T T T
2	Start p=2, check primes[2]	2	-	[false, false, true, true, true, true, true, true, true, true]	p=2, primes[2]=true
3	Mark multiples of 2 starting at 4	2	4,6,8	[false, false, true, true, false, true, false, true, false, true]	Marked 4,6,8 as false
4	Increment p=3, check primes[3]	3	-	[false, false, true, true, false, true, false, true, false, true]	p=3, primes[3]=true
5	Mark multiples of 3 starting at 9	3	9	[false, false, true, true, false, true, false, true, false, false]	Marked 9 as false
6	Increment p=4, check primes[4]	4	-	[false, false, true, true, false, true, false, true, false, false]	p=4, primes[4]=false, skip marking
7	Increment p=5, check p*p=25 > 9 stop	5	-	[false, false, true, true, false, true, false, true, false, false]	Stop as 5*5=25 > 9
8	Collect primes	-	-	[false, false, true, true, false, true, false, true, false, false]	Primes at indices 2,3,5,7

💡 Stop when p*p > n (5*5=25 > 9), then collect primes from array

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 6	Final
p	-	2	3	4	5
primes array	[F,F,T,T,T,T,T,T,T,T]	[F,F,T,T,F,T,F,T,F,T]	[F,F,T,T,F,T,F,T,F,F]	[F,F,T,T,F,T,F,T,F,F]	[F,F,T,T,F,T,F,T,F,F]

Key Moments - 3 Insights

Why do we start marking multiples from p*p and not from 2*p?

Because all smaller multiples of p (like 2*p, 3*p, ...) were already marked by smaller primes. See Step 3 where marking starts at 4 (2*2) for p=2.

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

Because any composite number less than or equal to n must have a factor less than or equal to sqrt(n). After p*p > n, no new multiples need marking. See Step 7 where p=5 and 5*5=25 > 9 stops the loop.

Why are 0 and 1 set to false at the start?

Because 0 and 1 are not prime numbers by definition. This is shown in Step 1 where primes[0] and primes[1] are set to false.

Visual Quiz - 3 Questions

Look at the execution table at Step 3. Which indices were marked as not prime?

A 4, 6, 8

B 3, 6, 9

C 2, 4, 6

D 5, 7, 9

💡 Hint

Check the 'Marking Multiples' column at Step 3 in the execution table.

At which step does the algorithm stop marking multiples because p*p > n?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'exit_note' and Step 7 in the execution table.

According to the variable tracker, what is the value of p after Step 5?

A 4

B 3

C 2

D 5

💡 Hint

Check the 'p' row in the variable tracker under 'After Step 5'.

Concept Snapshot

Sieve of Eratosthenes finds primes up to n by:
- Creating a boolean array marking all as prime initially
- Setting 0 and 1 as not prime
- For each p from 2 to sqrt(n), marking multiples of p as not prime starting at p*p
- Collecting indices still marked prime as the result

Full Transcript

The Sieve of Eratosthenes algorithm starts by creating an array of booleans representing numbers from 0 to n, all set to true except 0 and 1 which are not prime. It then iterates from p=2 upwards, marking multiples of p as not prime starting from p squared. This continues until p squared is greater than n. Finally, the algorithm collects all indices still marked true as prime numbers. The execution table shows each step, including marking multiples and skipping non-prime p values. The variable tracker follows the current p and the primes array state. Key moments clarify why marking starts at p squared and why the loop stops at sqrt(n). The visual quiz tests understanding of these steps.

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 to find all primes up to a limit.

3. Final Answer:

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

4. Quick Check:

   Sieve of Eratosthenes = Find primes [OK]

Hint: Remember: sieve filters out non-primes to find primes [OK]

Common Mistakes:

• Confusing it with sorting algorithms
• Thinking it finds factors instead of primes
• Assuming it works on strings

2. Which of the following JavaScript code snippets correctly initializes the sieve array for numbers up to n?

easy

A. const sieve = Array(n).fill(true); sieve[0] = sieve[1] = true;

B. const sieve = new Array(n).fill(false); sieve[0] = sieve[1] = true;

C. const sieve = new Array(n + 1).fill(true); sieve[0] = sieve[1] = false;

D. const sieve = new Array(n + 1).fill(false); sieve[0] = sieve[1] = false;

Solution

1. Step 1: Understand sieve initialization

   The sieve array should mark all numbers as true initially, except 0 and 1 which are not prime.

2. Step 2: Check each option

   const sieve = new Array(n + 1).fill(true); sieve[0] = sieve[1] = false; correctly creates an array of size n+1 filled with true, then sets 0 and 1 to false.

3. Final Answer:

   const sieve = new Array(n + 1).fill(true); sieve[0] = sieve[1] = false; -> Option C

4. Quick Check:

   Initialize sieve with true, except 0 and 1 false [OK]

Hint: Sieve size is n+1; 0 and 1 are not prime [OK]

Common Mistakes:

• Using size n instead of n+1
• Filling with false instead of true
• Marking 0 and 1 as true

3. What will be the output of the following code snippet?

function sieve(n) {
  const sieve = new Array(n + 1).fill(true);
  sieve[0] = sieve[1] = false;
  for (let i = 2; i * i <= n; i++) {
    if (sieve[i]) {
      for (let j = i * i; j <= n; j += i) {
        sieve[j] = false;
      }
    }
  }
  return sieve.map((val, idx) => val ? idx : null).filter(x => x);
}
console.log(sieve(10));

medium

A. [1, 2, 3, 5, 7]

B. [2, 3, 5, 7]

C. [2, 3, 4, 5, 7]

D. [2, 3, 5, 7, 9]

Solution

1. Step 1: Understand sieve marking

   The code marks multiples of primes as false, starting from i*i, up to n=10.

2. Step 2: Identify primes up to 10

   Primes are 2, 3, 5, 7. Numbers 1, 4, 6, 8, 9, 10 are marked false.

3. Final Answer:

   [2, 3, 5, 7] -> Option B

4. Quick Check:

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

Hint: Primes under 10 are 2,3,5,7 only [OK]

Common Mistakes:

• Including 1 as prime
• Including non-primes like 4 or 9
• Off-by-one errors in loops

4. Identify the error in the following Sieve of Eratosthenes implementation:

function sieve(n) {
  const sieve = new Array(n).fill(true);
  sieve[0] = sieve[1] = false;
  for (let i = 2; i <= n; i++) {
    if (sieve[i]) {
      for (let j = i * 2; j < n; j += i) {
        sieve[j] = false;
      }
    }
  }
  return sieve.map((val, idx) => val ? idx : null).filter(x => x);
}

medium

A. Array size should be n+1 to include number n

B. Inner loop should start from i*3 instead of i*2

C. Outer loop should run only up to sqrt(n)

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

Solution

1. Step 1: Check array size

   The array is created with size n, so index n is out of range and not included.

2. Step 2: Understand loop bounds

   To include number n, array size must be n+1; otherwise, sieve[n] is undefined.

3. Final Answer:

   Array size should be n+1 to include number n -> Option A

4. Quick Check:

   Array size = n+1 to cover all numbers [OK]

Hint: Array size must cover all indices up to n [OK]

Common Mistakes:

• Using array size n instead of n+1
• Looping outer loop beyond sqrt(n)
• Starting inner loop from i*3 incorrectly

5. You want to find all prime numbers between 50 and 100 using the Sieve of Eratosthenes. Which approach is correct?

hard

A. Run sieve up to 150 and ignore primes below 50

B. Run sieve only from 50 to 100 directly

C. Run sieve up to 50, then add primes from 51 to 100 manually

D. Run sieve up to 100, then filter primes >= 50 from the result

Solution

1. Step 1: Understand sieve range requirement

   The sieve finds primes from 2 up to the limit; partial ranges are not supported directly.

2. Step 2: Filter primes after full sieve

   Run sieve up to 100, then select primes >= 50 from the result for correct output.

3. Final Answer:

   Run sieve up to 100, then filter primes >= 50 from the result -> Option D

4. Quick Check:

   Sieve full range, then filter needed primes [OK]

Hint: Sieve full range, then filter start point [OK]

Common Mistakes:

• Trying to sieve partial ranges directly
• Ignoring primes below 50 without full sieve
• Manually adding primes without verification