Sieve of Eratosthenes Find All Primes in DSA Javascript - Deep Dive

Overview - Sieve of Eratosthenes Find All Primes

What is it?

The Sieve of Eratosthenes is a simple and efficient way to find all prime numbers up to a certain limit. It works by marking the multiples of each prime number starting from 2, so only primes remain unmarked. This method helps quickly identify primes without checking each number individually. It is one of the oldest algorithms known for this purpose.

Why it matters

Finding prime numbers is important in many areas like cryptography, computer security, and math problems. Without an efficient way like the sieve, checking primes would be slow and costly for large numbers. This algorithm saves time and computing power, making tasks that rely on primes much faster and more practical.

Where it fits

Before learning this, you should understand basic loops, arrays, and the concept of prime numbers. After this, you can explore more advanced prime-finding methods or use primes in cryptography and number theory problems.

Mental Model

Core Idea

Start with all numbers marked as possible primes, then repeatedly mark multiples of each found prime as not prime, leaving only primes unmarked.

Think of it like...

Imagine a classroom with students numbered from 2 to the last seat. You first mark every student who is a multiple of 2 as absent, then every multiple of 3, then 5, and so on. At the end, only students who were never marked absent are present -- these are the prime numbers.

Numbers: 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Step 1: Mark multiples of 2 -> 4,6,8,10,12,14 marked
Step 2: Mark multiples of 3 -> 6,9,12,15 marked
Remaining unmarked: 2,3,5,7,11,13 (primes)

Build-Up - 6 Steps

1

Foundation

Understanding Prime Numbers

Concept: Learn what prime numbers are and why they matter.

A prime number is a number greater than 1 that has no divisors other than 1 and itself. For example, 2, 3, 5, and 7 are primes because you cannot divide them evenly by any other number. Knowing primes helps in many math and computer problems.

Result

You can identify prime numbers by checking divisibility.

Understanding what makes a number prime is the foundation for any prime-finding method.

2

Foundation

Basic Array Marking Technique

Concept: Use an array to keep track of which numbers are prime candidates.

Create an array where each index represents a number. Initially, mark all as true (possible prime). We will change some to false as we find they are not prime.

Result

An array of booleans representing prime status for each number.

Using an array to track primes lets us efficiently update and check numbers.

3

Intermediate

Marking Multiples as Not Prime

🤔Before reading on: do you think marking multiples of a prime should start from 2 times the prime or the prime squared? Commit to your answer.

Concept: Mark all multiples of each prime number as not prime, starting from its square.

For each number starting from 2, if it is still marked true, mark all its multiples as false. We start marking from the square of the number because smaller multiples were already marked by smaller primes.

Result

Non-prime numbers are marked false, primes remain true.

Starting from the square avoids redundant work and speeds up the algorithm.

4

Intermediate

Stopping at Square Root Limit

🤔Before reading on: do you think we need to check numbers beyond the square root of the limit? Commit to yes or no.

Concept: You only need to mark multiples up to the square root of the maximum number.

If a number has a factor larger than its square root, it must also have a smaller factor. So, checking beyond the square root is unnecessary.

Result

Algorithm runs faster by limiting the marking process.

Knowing when to stop reduces unnecessary checks and improves efficiency.

5

Advanced

Implementing the Sieve in JavaScript

🤔Before reading on: do you think the sieve requires nested loops or a single loop? Commit to your answer.

Concept: Write JavaScript code that creates the sieve and outputs all primes up to a limit.

const sieveOfEratosthenes = limit => { const sieve = Array(limit + 1).fill(true); sieve[0] = false; sieve[1] = false; for (let i = 2; i * i <= limit; i++) { if (sieve[i]) { for (let j = i * i; j <= limit; j += i) { sieve[j] = false; } } } const primes = []; for (let i = 2; i <= limit; i++) { if (sieve[i]) primes.push(i); } return primes; }; console.log(sieveOfEratosthenes(20));

Result

[2, 3, 5, 7, 11, 13, 17, 19]

Seeing the full code connects the theory to practical implementation.

6

Expert

Memory and Performance Optimizations

🤔Before reading on: do you think storing all numbers as booleans is always efficient? Commit to yes or no.

Concept: Explore ways to reduce memory and speed up the sieve, like using bit arrays or skipping even numbers.

The basic sieve uses an array of booleans, which can be large for big limits. Using a bit array reduces memory by storing multiple flags per byte. Also, since all even numbers except 2 are not prime, we can skip them to halve the work. These optimizations make the sieve practical for very large ranges.

Result

More efficient sieve that uses less memory and runs faster on large inputs.

Understanding these optimizations is key for applying the sieve in real-world, large-scale problems.

Under the Hood

The sieve works by iteratively marking multiples of each prime number as composite (not prime). It starts with an array where all numbers are assumed prime. When a prime is found, its multiples are marked false. This process uses the fact that every composite number has a prime factor less than or equal to its square root, so marking beyond that is unnecessary.

Why designed this way?

The sieve was designed to avoid checking divisibility for every number individually, which is slow. By marking multiples in bulk, it reduces repeated work. Starting marking from the square of the prime avoids redundant marking of smaller multiples already handled by smaller primes. This design balances simplicity and efficiency.

┌───────────────┐
│ Initialize    │
│ array of true │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ For i = 2 to  │
│ sqrt(limit):  │
│ if true, mark │
│ multiples     │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Mark multiples│
│ from i*i to   │
│ limit as false│
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Collect all   │
│ indices true  │
│ as primes     │
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Do you think the sieve marks multiples starting from 2 times the prime? Commit yes or no.

Common Belief: The sieve marks multiples starting from 2 times the prime number.

Reality: The sieve actually starts marking from the square of the prime number because smaller multiples were already marked by smaller primes.

Why it matters: Starting from 2 times the prime causes redundant work and slows down the algorithm unnecessarily.

Quick: Do you think the sieve needs to check numbers beyond the square root of the limit? Commit yes or no.

Common Belief: The sieve must check all numbers up to the limit to mark multiples.

Reality: It only needs to check numbers up to the square root of the limit because larger factors have smaller complementary factors already checked.

Why it matters: Checking beyond the square root wastes time and resources without adding value.

Quick: Do you think the sieve can find primes instantly without any iteration? Commit yes or no.

Common Belief: The sieve instantly knows which numbers are prime without looping through multiples.

Reality: The sieve requires looping through numbers and marking multiples to identify primes; it is not instantaneous.

Why it matters: Expecting instant results can lead to misunderstanding the algorithm's process and complexity.

Expert Zone

1

The sieve can be optimized by only storing odd numbers, halving memory and computation.

2

Bit arrays can store prime flags compactly, improving cache performance and reducing memory footprint.

3

Segmented sieves allow finding primes in very large ranges without storing the entire array at once.

When NOT to use

For extremely large numbers beyond memory limits, or when checking primality of a single large number, probabilistic tests like Miller-Rabin are better. The sieve is best for finding all primes up to a moderate limit.

Production Patterns

Used in cryptography key generation, prime-based hashing, and mathematical software. Often combined with segmented or wheel sieves for efficiency in large-scale prime generation.

Connections

Bit Manipulation

The sieve's boolean array can be optimized using bit manipulation techniques.

Understanding bit operations helps implement memory-efficient prime sieves.

Cryptography

Prime numbers found by the sieve are foundational for cryptographic algorithms like RSA.

Knowing how primes are generated helps understand the security basis of encryption.

Epidemiology Modeling

Both use iterative marking processes to track spread or elimination (primes or infections).

Recognizing similar marking patterns across fields reveals common problem-solving strategies.

Common Pitfalls

#1 Starting to mark multiples from 2 times the prime instead of its square.

Wrong approach:

for (let j = i * 2; j <= limit; j += i) {
sieve[j] = false;
}

Correct approach:

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

Root cause:

Misunderstanding that smaller multiples are already marked by smaller primes.

#2 Checking numbers beyond the square root of the limit for marking multiples.

Wrong approach:

for (let i = 2; i <= limit; i++) {
if (sieve[i]) { /* mark multiples */ }
}

Correct approach:

for (let i = 2; i * i <= limit; i++) {
if (sieve[i]) { /* mark multiples */ }
}

Root cause:

Not knowing the mathematical property that factors above the square root are redundant.

#3 Including 0 and 1 as prime numbers in the output.

Wrong approach:

const sieve = Array(limit + 1).fill(true);
// no marking sieve[0] and sieve[1] as false
// output primes including 0 and 1

Correct approach:

sieve[0] = false;
sieve[1] = false;
// output primes starting from 2

Root cause:

Forgetting that 0 and 1 are not prime by definition.

Key Takeaways

The Sieve of Eratosthenes efficiently finds all primes up to a limit by marking multiples of primes as not prime.

Starting to mark multiples from the square of the prime and stopping at the square root of the limit are key optimizations.

Using an array to track prime status allows bulk marking and quick final collection of primes.

Advanced optimizations like bit arrays and segmented sieves make the algorithm practical for very large ranges.

Understanding the sieve deepens knowledge of prime numbers and their role in computing and cryptography.

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