Sieve of Eratosthenes Find All Primes in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sieve for n=10

What is the output of the following TypeScript code that uses the Sieve of Eratosthenes to find all primes up to 10?

DSA Typescript

function sieve(n: number): number[] {
  const primes = new Array(n + 1).fill(true);
  primes[0] = false;
  primes[1] = false;
  for (let i = 2; i * i <= n; i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }
  const result: number[] = [];
  for (let i = 2; i <= n; i++) {
    if (primes[i]) result.push(i);
  }
  return result;
}
console.log(sieve(10));

A [2, 3, 4, 5, 7]

B [2, 3, 5, 7]

C [2, 3, 5, 7, 9]

D [1, 2, 3, 5, 7]

💡 Hint

Remember that primes are numbers greater than 1 with no divisors other than 1 and themselves.

The sieve marks multiples of each prime as false. Numbers 4, 6, 8, 9, and 10 are not prime. Only 2, 3, 5, and 7 remain true.

❓ Predict Output

intermediate

Number of primes up to 20

How many prime numbers does the following code find up to 20?

DSA Typescript

function sieveCount(n: number): number {
  const primes = new Array(n + 1).fill(true);
  primes[0] = false;
  primes[1] = false;
  for (let i = 2; i * i <= n; i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }
  let count = 0;
  for (let i = 2; i <= n; i++) {
    if (primes[i]) count++;
  }
  return count;
}
console.log(sieveCount(20));

A 8

B 9

C 7

D 10

💡 Hint

Count primes: 2,3,5,7,11,13,17,19

The primes up to 20 are 2, 3, 5, 7, 11, 13, 17, and 19, totaling 8 primes.

🧠 Conceptual

advanced

Why does the inner loop start at i*i?

In the Sieve of Eratosthenes, why does the inner loop start marking multiples from i*i instead of 2*i?

A Because starting at 2*i would miss some multiples.

B Because i*i is the smallest prime number.

C Because all smaller multiples of i have already been marked by smaller primes.

D Because i*i is always a prime number.

💡 Hint

Think about when multiples get marked in previous steps.

Multiples less than i*i are already marked by smaller primes, so starting at i*i avoids redundant work.

❓ Predict Output

advanced

Output of sieve with n=1

What is the output of the following code when n=1?

DSA Typescript

function sieve(n: number): number[] {
  const primes = new Array(n + 1).fill(true);
  primes[0] = false;
  primes[1] = false;
  for (let i = 2; i * i <= n; i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }
  const result: number[] = [];
  for (let i = 2; i <= n; i++) {
    if (primes[i]) result.push(i);
  }
  return result;
}
console.log(sieve(1));

A [2]

B [1]

C [0]

D []

💡 Hint

Primes start from 2.

Since n=1, no numbers 2 or greater exist, so the result is an empty list.

🔧 Debug

expert

Identify the error in this sieve implementation

What error does the following code produce when run with n=10?

DSA Typescript

function sieve(n: number): number[] {
  const primes = new Array(n + 1).fill(true);
  primes[0] = false;
  primes[1] = false;
  for (let i = 2; i <= n / 2; i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }
  const result: number[] = [];
  for (let i = 2; i <= n; i++) {
    if (primes[i]) result.push(i);
  }
  return result;
}
console.log(sieve(10));

A The code runs correctly and outputs [2, 3, 5, 7]

B The code outputs [2, 3, 5, 7, 9, 11]

C The code outputs [2, 3, 5, 7, 9, 10]

D The code outputs [2, 3, 5, 7, 9]

💡 Hint

Check the loop condition for i in the outer loop.

The code runs correctly for n=10 and outputs [2, 3, 5, 7]. The outer loop condition i <= n/2 works but is suboptimal; the standard Sieve uses i * i <= n to limit the outer loop to sqrt(n) for better efficiency.

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