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

Concept Flow - Sieve of Eratosthenes Find All Primes

Initialize array of size n+1 with True

↓

Set 0 and 1 to False

↓

Start with p = 2

↓

Is p * p <= n?

No→Collect primes where True

Yes↓

Mark multiples of p as False

↓

Increment p

↩Back to check p * p <= n

Start with all numbers marked prime, then repeatedly mark multiples of each prime as not prime until p squared exceeds n, then collect all primes.

Execution Sample

DSA Typescript

function sieve(n: number): number[] {
  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.reduce((acc, val, idx) => val ? [...acc, idx] : acc, []);
}

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)
1	Initialize array	-	-	[T, T, T, T, T, T, T, T, T, T, T]
2	Set 0 and 1 to False	-	-	[F, F, T, T, T, T, T, T, T, T, T]
3	Check p=2, 2*2=4 <= 10	2	-	[F, F, T, T, T, T, T, T, T, T, T]
4	Mark multiples of 2 starting at 4	2	4,6,8,10	[F, F, T, T, F, T, F, T, F, T, F]
5	Increment p to 3	3	-	[F, F, T, T, F, T, F, T, F, T, F]
6	Check p=3, 3*3=9 <= 10	3	-	[F, F, T, T, F, T, F, T, F, T, F]
7	Mark multiples of 3 starting at 9	3	9	[F, F, T, T, F, T, F, T, F, F, F]
8	Increment p to 4	4	-	[F, F, T, T, F, T, F, T, F, F, F]
9	Check p=4, 4*4=16 > 10, stop	4	-	[F, F, T, T, F, T, F, T, F, F, F]
10	Collect primes where True	-	-	Primes: [2,3,5,7]

💡 Stop when p squared (16) is greater than n (10), then collect all indices marked True as primes.

Variable Tracker

Variable	Start	After Step 4	After Step 7	Final
primes	[F,F,T,T,T,T,T,T,T,T,T]	[F,F,T,T,F,T,F,T,F,T,F]	[F,F,T,T,F,T,F,T,F,F,F]	[F,F,T,T,F,T,F,T,F,F,F]
p	2	2	3	4
Marked Multiples	-	4,6,8,10	9	-

Key Moments - 3 Insights

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

Because smaller multiples like 2*p, 3*p, etc. were already marked by smaller primes. See execution_table rows 4 and 7 where marking starts at p*p.

Why does the loop stop 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). See execution_table row 9 where p=4 and 4*4=16 > 10 stops the loop.

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

Because 0 and 1 are not prime numbers. This is shown in execution_table row 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of primes[6] after step 4?

A False

B True

C Undefined

D Not changed

💡 Hint

Check the Array State column at step 4 in execution_table.

At which step does the algorithm stop marking multiples?

A Step 7

B Step 5

C Step 9

D Step 10

💡 Hint

Look at the exit_note and step 9 in execution_table where p*p > n.

If we change n to 20, how would the marking multiples step change compared to step 4?

A Fewer multiples of 2 would be marked False

B More multiples of 2 would be marked False

C No multiples of 2 would be marked False

D Only multiples of 3 would be marked False

💡 Hint

Increasing n increases the range, so more multiples of 2 up to n would be marked False.

Concept Snapshot

Sieve of Eratosthenes finds primes up to n by:
- Creating a boolean array marking all as True
- Setting 0 and 1 to False
- For p from 2 to sqrt(n), mark multiples of p starting at p*p as False
- Collect indices still True as primes
This efficiently removes non-primes by crossing out multiples.

Full Transcript

The Sieve of Eratosthenes algorithm starts by assuming all numbers from 0 to n are prime except 0 and 1. It then iterates from p=2 up to the square root of n. For each p that is still marked prime, it marks all multiples of p starting from p squared as not prime. This process continues until p squared is greater than n. Finally, all numbers still marked prime are collected as the list of primes up to n. The key optimization is starting marking multiples at p squared because smaller multiples were already handled by smaller primes. This method efficiently finds all primes up to n.

Practice

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

easy

A. To find the greatest common divisor of two numbers

B. To sort an array of numbers

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

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 the limit.

3. Final Answer:

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

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 or reverses strings
• Assuming it works for negative numbers

2. Which of the following is the correct TypeScript syntax to initialize a boolean array named isPrime of size n+1 with all values set to true?

easy

A. const isPrime = Array(n + 1).fill(false);

B. const isPrime = new Array(n + 1).fill(true);

C. const isPrime = new Array(n).fill(true);

D. const isPrime = new Boolean[n + 1];

Solution

1. Step 1: Check array size and initialization

   We need an array of size n+1 to include index n, filled with true values.

2. Step 2: Verify TypeScript syntax

   Using new Array(n + 1).fill(true) correctly creates and fills the array.

3. Final Answer:

   const isPrime = new Array(n + 1).fill(true); -> Option B

4. Quick Check:

   Correct array init = const isPrime = new Array(n + 1).fill(true); [OK]

Hint: Use new Array(size).fill(value) to initialize arrays [OK]

Common Mistakes:

• Using wrong size (n instead of n+1)
• Filling with false instead of true
• Incorrect syntax like Boolean[n + 1]

3. What will be the output array isPrime after running the Sieve of Eratosthenes for n = 10? (true means prime, false means not prime)

medium

A. [false, false, true, true, false, true, false, true, false, false, false]

B. [false, false, true, true, true, true, false, true, false, false, true]

C. [false, false, true, true, false, true, false, true, false, false, true]

D. [false, true, true, true, false, true, false, true, false, false, false]

Solution

1. Step 1: Initialize array for n=10

   Indices 0 and 1 are not prime, so false. Indices 2 to 10 start as true.

2. Step 2: Mark multiples of primes as false

   Multiples of 2: 4,6,8,10 -> false; multiples of 3: 6,9 -> false; others remain true.

3. Final Answer:

   [false, false, true, true, false, true, false, true, false, false, false] -> Option A

4. Quick Check:

   Prime flags for 2-10 = [false, false, true, true, false, true, false, true, false, false, false] [OK]

Hint: Mark multiples of each prime starting from its square [OK]

Common Mistakes:

• Marking 1 as prime
• Not marking multiples correctly
• Confusing true/false meanings

4. Consider this TypeScript snippet for the sieve:

const n = 10;
const isPrime = new Array(n + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;
for (let i = 2; i <= n; i++) {
  if (isPrime[i]) {
    for (let j = i * 2; j <= n; j += i) {
      isPrime[j] = false;
    }
  }
}
console.log(isPrime);

What is the main issue with this code?

medium

A. The inner loop should start from i * i instead of i * 2

B. The array size is incorrect, should be n instead of n+1

C. The outer loop should run until i < n, not i <= n

D. The initial values of isPrime[0] and isPrime[1] should be true

Solution

1. Step 1: Analyze inner loop start

   Starting from i*2 marks some multiples multiple times, causing inefficiency.

2. Step 2: Correct starting point for marking multiples

   Starting from i*i is optimal because smaller multiples were marked by smaller primes.

3. Final Answer:

   The inner loop should start from i * i instead of i * 2 -> Option A

4. Quick Check:

   Start inner loop at i*i for efficiency = The inner loop should start from i * i instead of i * 2 [OK]

Hint: Start marking multiples from i squared to avoid repeats [OK]

Common Mistakes:

• Starting inner loop at i*2 wastes time
• Incorrect array size assumptions
• Wrong initialization of 0 and 1 as prime

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

hard

A. 11

B. 12

C. 9

D. 10

Solution

1. Step 1: List primes up to 30

   Primes are 2,3,5,7,11,13,17,19,23,29.

2. Step 2: Count the primes

   Counting these primes gives 10 primes up to 30.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Count primes ≤ 30 = 10 [OK]

Hint: Count primes manually or trust sieve output for small n [OK]

Common Mistakes:

• Including 1 as prime
• Counting primes beyond n
• Miscounting primes between 20 and 30