Sieve of Eratosthenes Find All Primes in DSA Typescript - 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 for prime number generation.

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 hard 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 mastering the sieve, you can explore more advanced prime tests, factorization methods, and applications in cryptography or number theory.

Mental Model

Core Idea

Start with all numbers marked as possible primes, then repeatedly remove multiples of each found prime to leave only primes unmarked.

Think of it like...

Imagine a classroom where every student is initially standing. The teacher asks every second student to sit down, then every third standing student to sit down, and so on. At the end, only students who never had to sit down remain standing -- these are the primes.

Numbers:  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Step 1:  Mark multiples of 2 -> 4,6,8,10,12,14,16 sit down
Step 2:  Mark multiples of 3 -> 6,9,12,15 sit down
Step 3:  Next prime 5, mark multiples -> 10,15 sit down
Remaining standing: 2 3 5 7 11 13

Build-Up - 7 Steps

1

Foundation

Understanding Prime Numbers

Concept: Introduce 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. Numbers like 4 or 6 are not prime because they can be divided evenly by numbers other than 1 and themselves.

Result

You know which numbers are prime and which are not by definition.

Understanding what primes are is essential because the sieve's goal is to find all such numbers efficiently.

2

Foundation

Marking Multiples to Remove Non-Primes

Concept: Introduce the idea of removing multiples of a number to find primes.

If a number is not prime, it must be a multiple of a smaller prime. For example, 6 is a multiple of 2 and 3. So, if we remove all multiples of 2, 3, 5, etc., only primes remain. This is the key idea behind the sieve.

Result

You understand that removing multiples helps isolate primes.

Knowing that non-primes are multiples of primes allows us to filter numbers systematically.

3

Intermediate

Creating and Initializing the Sieve Array

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

We create an array of booleans from 0 to n, initially marking all numbers as true (possible primes) except 0 and 1 which are not prime. This array helps us keep track of which numbers are still candidates.

Result

An array like [false, false, true, true, true, ..., true] ready for marking.

Using an array to track candidates makes the process efficient and easy to implement.

4

Intermediate

Iterating and Marking Multiples Efficiently

🤔Before reading on: Do you think we should mark multiples starting from 2 or from the square of the prime? Commit to your answer.

Concept: Start marking multiples from the square of the current prime to avoid redundant work.

For each number starting from 2 up to the square root of n, if it is still marked true, mark all its multiples starting from its square as false. Starting from the square is enough because smaller multiples were already marked by smaller primes.

Result

Only prime numbers remain marked true in the array after this process.

Starting from the square reduces unnecessary checks and speeds up the algorithm.

5

Intermediate

Extracting the List of Primes

Concept: Collect all numbers still marked true as primes.

After marking multiples, loop through the array and collect all indices marked true. These indices represent prime numbers up to n.

Result

A list of primes like [2, 3, 5, 7, 11, 13, ...] is produced.

Separating the marking and collecting steps clarifies the algorithm and makes it easier to use.

6

Advanced

TypeScript Implementation of the Sieve

🤔Before reading on: Do you think the sieve code will use nested loops or recursion? Commit to your answer.

Concept: Implement the sieve using loops and boolean arrays in TypeScript.

function sieveOfEratosthenes(n: number): number[] { 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: number[] = []; for (let i = 2; i <= n; i++) { if (isPrime[i]) primes.push(i); } return primes; } // Example usage: console.log(sieveOfEratosthenes(20));

Result

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

Seeing the full code connects the theory to practice and shows how simple the sieve is to implement.

7

Expert

Optimizations and Memory Considerations

🤔Before reading on: Do you think storing all numbers up to n is always efficient? Commit to your answer.

Concept: Discuss memory use and possible optimizations like using bit arrays or skipping even numbers.

The sieve uses an array of size n+1, which can be large for big n. To save memory, we can store only odd numbers since even numbers >2 are not prime. Also, using bits instead of booleans reduces space. These optimizations improve performance in real-world applications.

Result

More memory-efficient sieve implementations that scale better for large inputs.

Understanding memory tradeoffs is crucial for applying the sieve in large-scale or resource-limited environments.

Under the Hood

The sieve works by iteratively marking multiples of each prime number as non-prime in a boolean array. Initially, all numbers are assumed prime. When a prime is found, its multiples are marked false starting from its square because smaller multiples were already handled by smaller primes. This process continues up to the square root of the limit, ensuring all non-primes are marked. The remaining true values correspond to primes.

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 from the square of each prime avoids redundant marking. This design balances simplicity and efficiency, making it practical even before modern computers.

┌───────────────┐
│ Initialize    │
│ array with    │
│ true values   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ For i = 2 to  │
│ sqrt(n):      │
│ if isPrime[i] │
│ mark multiples│
│ from i*i as   │
│ false        │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Collect all   │
│ indices with  │
│ true as primes│
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the sieve check divisibility of every number by every smaller number? Commit yes or no.

Common Belief: The sieve tests each number by dividing it by all smaller numbers to check if it is prime.

Reality: The sieve does not perform division checks; it marks multiples of primes directly, avoiding repeated division.

Why it matters: Believing the sieve does division checks leads to misunderstanding its efficiency and may cause learners to write slower code.

Quick: Is it necessary to mark multiples starting from 2 times the prime? Commit yes or no.

Common Belief: We must mark multiples starting from 2 times the prime number to remove all non-primes.

Reality: Marking starts from the square of the prime 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.

Quick: Does the sieve find primes beyond the input limit n? Commit yes or no.

Common Belief: The sieve can find primes larger than the given limit n by extending the array automatically.

Reality: The sieve only finds primes up to the specified limit n; it does not extend beyond it.

Why it matters: Expecting primes beyond n leads to incorrect assumptions about the algorithm's output and misuse.

Quick: Can the sieve be used to check if a single large number is prime efficiently? Commit yes or no.

Common Belief: The sieve is the best method to check if a single large number is prime.

Reality: The sieve is efficient for finding all primes up to n, but for a single large number, other tests like Miller-Rabin are better.

Why it matters: Using the sieve for single large prime checks wastes time and memory.

Expert Zone

1

The sieve's efficiency depends heavily on starting marking from the square of each prime, which avoids redundant work.

2

Memory usage can be halved by ignoring even numbers, but this requires careful index mapping in the array.

3

Bit arrays can be used instead of boolean arrays to reduce memory footprint, but they add complexity in bit manipulation.

When NOT to use

Avoid using the sieve when checking primality of very large single numbers or when memory is extremely limited. Instead, use probabilistic primality tests like Miller-Rabin or deterministic tests optimized for large inputs.

Production Patterns

In production, the sieve is often used to precompute primes for cryptographic key generation or mathematical libraries. It is combined with segmented sieves to handle very large ranges without excessive memory use.

Connections

Bit Manipulation

Builds-on

Using bit arrays to store prime flags in the sieve reduces memory usage drastically, showing how low-level data representation improves algorithm efficiency.

Cryptography

Application

Understanding prime generation with the sieve helps grasp how cryptographic keys are created, as primes are fundamental to encryption algorithms.

Filtering in Signal Processing

Similar pattern

Both the sieve and signal filters remove unwanted elements from a set, illustrating a shared concept of systematic elimination to isolate desired components.

Common Pitfalls

#1 Marking multiples starting from 2 times the prime instead of its square.

Wrong approach:

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

Correct approach:

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

Root cause:

Misunderstanding that smaller multiples are already handled by smaller primes leads to redundant marking and slower code.

#2 Initializing all numbers including 0 and 1 as prime candidates.

Wrong approach:

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

Correct approach:

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

Root cause:

Forgetting that 0 and 1 are not prime causes incorrect results.

#3 Using the sieve to check primality of a single large number.

Wrong approach:

const primes = sieveOfEratosthenes(1000000000);
return primes.includes(largeNumber);

Correct approach:

Use a primality test like Miller-Rabin for large single numbers instead of the sieve.

Root cause:

Misapplying the sieve beyond its intended use wastes resources and time.

Key Takeaways

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

Starting to mark multiples from the square of each prime avoids redundant work and speeds up the algorithm.

Using a boolean array to track prime candidates makes the sieve simple and fast to implement.

Memory optimizations like ignoring even numbers or using bit arrays improve the sieve's scalability.

The sieve is best for generating many primes, but other methods are better for checking single large primes.

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