Sieve of Eratosthenes Find All Primes in DSA Typescript - Build from Scratch

Sieve of Eratosthenes Find All Primes

📖 Scenario: You are helping a teacher prepare a list of prime numbers for a math class. The teacher wants to find all prime numbers up to a certain number using a fast method called the Sieve of Eratosthenes.

🎯 Goal: Build a TypeScript program that uses the Sieve of Eratosthenes to find and print all prime numbers up to a given number.

📋 What You'll Learn

Create an array to represent numbers from 0 to the given limit

Use a boolean array to mark numbers as prime or not

Implement the Sieve of Eratosthenes logic to mark multiples as not prime

Print the list of prime numbers found

💡 Why This Matters

🌍 Real World

Finding prime numbers is useful in cryptography, computer security, and number theory research.

💼 Career

Understanding prime number algorithms helps in software development roles involving security, algorithms, and performance optimization.

1

Create the number limit and initialize the sieve array

Create a variable called limit and set it to 30. Then create a boolean array called isPrime with size limit + 1 where all values are initially true except for indices 0 and 1 which should be false.

DSA Typescript

// Create the limit and initialize the isPrime array
// Your code here

Hint

Use new Array(limit + 1).fill(true) to create the boolean array. Then set isPrime[0] and isPrime[1] to false because 0 and 1 are not prime.

2

Set the starting point for the sieve loop

Create a variable called start and set it to 2. This will be the first number to check for marking multiples.

DSA Typescript

const limit = 30;
const isPrime: boolean[] = new Array(limit + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;
// Create the start variable
// Your code here

Hint

The sieve starts checking from 2, the smallest prime number.

3

Implement the Sieve of Eratosthenes logic

Use a for loop with variable num starting from start up to and including Math.sqrt(limit). Inside it, use an if statement to check if isPrime[num] is true. If yes, use another for loop with variable multiple starting from num * num up to limit, incrementing by num. Inside this inner loop, set isPrime[multiple] to false.

DSA Typescript

const limit = 30;
const isPrime: boolean[] = new Array(limit + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;
const start = 2;
// Implement the sieve loops
// Your code here

Hint

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

4

Print all prime numbers found

Use a for loop with variable i from 2 to limit. Inside the loop, use an if statement to check if isPrime[i] is true. If yes, print i followed by a space on the same line. After the loop, print a newline.

DSA Typescript

const limit = 30;
const isPrime: boolean[] = new Array(limit + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;
const start = 2;

for (let num = start; num <= Math.sqrt(limit); num++) {
    if (isPrime[num]) {
        for (let multiple = num * num; multiple <= limit; multiple += num) {
            isPrime[multiple] = false;
        }
    }
}
// Print all primes
// Your code here

Hint

Collect all prime numbers in a string separated by spaces and print it once after the loop.

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