Sieve of Eratosthenes Find All Primes in DSA Javascript

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 houses. We paint all houses that are multiples of a number red, leaving only prime-numbered houses unpainted.

Numbers: 2 3 4 5 6 7 8 9 10
Marks:  _ _ x _ x _ x x  x
_ means unmarked (potential prime), x means marked (not prime)

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: Start with list 2 to 10, all unmarked

2 3 4 5 6 7 8 9 10
_ _ _ _ _ _ _ _  _

Why: We begin assuming all numbers are prime candidates

Step 2: Mark multiples of 2 (except 2) as not prime

2 3 4 5 6 7 8 9 10
_ _ x _ x _ x _  x

Why: Multiples of 2 cannot be prime

Step 3: Move to next unmarked number 3, mark multiples of 3

2 3 4 5 6 7 8 9 10
_ _ x _ x _ x x  x

Why: Multiples of 3 are not prime

Step 4: Next unmarked number is 5, mark multiples of 5 (none in range)

2 3 4 5 6 7 8 9 10
_ _ x _ x _ x x  x

Why: No multiples of 5 to mark within 10

Step 5: Next unmarked number is 7, mark multiples of 7 (none in range)

2 3 4 5 6 7 8 9 10
_ _ x _ x _ x x  x

Why: No multiples of 7 to mark within 10

Result:

Primes are numbers with _ marks: 2 3 5 7

Annotated Code

DSA Javascript

class SieveOfEratosthenes {
  static findPrimes(n) {
    const isPrime = 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 = [];
    for (let i = 2; i <= n; i++) {
      if (isPrime[i]) primes.push(i);
    }
    return primes;
  }
}

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

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

Initialize array assuming all numbers are prime candidates

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

0 and 1 are not prime by definition

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

Check numbers up to square root of n for marking multiples

if (isPrime[i]) {

Only mark multiples if current number is still prime

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

Mark all multiples of i starting from i squared as not prime

isPrime[j] = false;

Mark multiple j as not prime

for (let i = 2; i <= n; i++) { 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: Better than checking each number's divisibility individually which is O(n sqrt n)

Edge Cases

n = 0 or n = 1

Returns empty list since no primes exist

DSA Javascript

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

n = 2

Returns [2] as the only prime

DSA Javascript

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

n is large but small primes only

Correctly marks multiples and returns primes up to n

DSA Javascript

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

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
Fix: Start marking multiples from i squared to avoid redundant marking

Mistake: Not marking 0 and 1 as not prime
Fix: Explicitly set isPrime[0] and isPrime[1] to false before starting

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 candidate.

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