Sieve of Eratosthenes Find All Primes in DSA Typescript

Mental Model

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

Analogy: Imagine a list of houses numbered 2 to n. You paint all houses that are multiples of 2, then multiples of 3, and so on. Houses left unpainted are special (prime).

Index: 2 3 4 5 6 7 8 9 10
Value: T T F T F T F F F
T = true means prime candidate

Dry Run Walkthrough

Input: Find all primes up to 10

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

Step 1: Start with all numbers 2 to 10 marked true (prime candidates)

2:T 3:T 4:T 5:T 6:T 7:T 8:T 9:T 10:T

Why: We assume all numbers are prime initially

Step 2: Mark multiples of 2 (except 2) as false

2:T 3:T 4:F 5:T 6:F 7:T 8:F 9:T 10:F

Why: Multiples of 2 cannot be prime

Step 3: Move to next true number 3, mark multiples of 3 as false

2:T 3:T 4:F 5:T 6:F 7:T 8:F 9:F 10:F

Why: Multiples of 3 cannot be prime

Step 4: Next true number is 5, mark multiples of 5 (none ≤10 except 10 already false)

2:T 3:T 4:F 5:T 6:F 7:T 8:F 9:F 10:F

Why: No new multiples to mark for 5 within range

Step 5: Next true number is 7, mark multiples of 7 (none ≤10)

2:T 3:T 4:F 5:T 6:F 7:T 8:F 9:F 10:F

Why: No new multiples to mark for 7 within range

Result:

2:T 3:T 4:F 5:T 6:F 7:T 8:F 9:F 10:F
Primes: 2, 3, 5, 7

Annotated Code

DSA Typescript

class SieveOfEratosthenes {
  static findPrimes(n: number): number[] {
    const isPrime: boolean[] = new Array(n + 1).fill(true);
    isPrime[0] = false;
    isPrime[1] = false;

    for (let i = 2; i * i <= n; i++) {
      if (isPrime[i]) {
        for (let j = i * i; j <= n; j += i) {
          isPrime[j] = false;
        }
      }
    }

    const primes: number[] = [];
    for (let i = 2; i <= n; i++) {
      if (isPrime[i]) primes.push(i);
    }
    return primes;
  }
}

const primesUpTo10 = SieveOfEratosthenes.findPrimes(10);
console.log(primesUpTo10.join(", "));

for (let i = 2; i * i <= n; i++) {

iterate from 2 up to square root of n to mark multiples

if (isPrime[i]) {

only mark multiples if current number is still prime

for (let j = i * i; j <= n; j += i) {

mark multiples of i starting from i squared as not prime

isPrime[j] = false;

mark multiple j as not prime

if (isPrime[i]) primes.push(i);

collect all numbers still marked prime

Output

2, 3, 5, 7

Complexity Analysis

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

Space: O(n) because we store a boolean array for all numbers up to n

vs Alternative: Much faster than checking each number's divisibility individually which is O(n sqrt n)

Edge Cases

n less than 2

Returns empty list since no primes exist below 2

DSA Typescript

isPrime[0] = false; isPrime[1] = false;

n equals 2

Returns [2] as the only prime

DSA Typescript

for (let i = 2; i * i <= n; i++) {

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 inner loop from i*2 instead of i*i, causing redundant marking
Fix: Start marking multiples from i squared to avoid re-marking smaller multiples

Summary

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

Use when you need all primes up to n efficiently.

Start marking multiples from the square of each prime to avoid redundant work.

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