Sieve of Eratosthenes Find All Primes in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create an array of boolean values initialized to true.

DSA Typescript

const sieve: boolean[] = new Array(n + 1).fill([1]);

Drag options to blanks, or click blank then click option'

Anull

Bfalse

Ctrue

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with false will mark all numbers as non-prime from the start.

Using null or undefined will cause errors when checking values.

The sieve array should be initialized with true to mark all numbers as potential primes initially.

2fill in blank

medium

Complete the for loop to start crossing out multiples from the first prime number.

DSA Typescript

for (let i = 2; i <= [1]; i++) {

Drag options to blanks, or click blank then click option'

AMath.sqrt(n)

Bn

Cn / 2

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Checking all numbers up to n is inefficient.

Using n/2 or n-1 is unnecessary and slows down the algorithm.

We only need to check numbers up to the square root of n because larger factors will have smaller complementary factors already checked.

3fill in blank

hard

Fix the error in the inner loop to mark multiples of i as non-prime.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Ai

Bj

C2

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using j as step causes an infinite loop or wrong increments.

Using 2 or 1 does not correctly mark multiples of i.

We increase j by i each time to mark all multiples of i as non-prime.

4fill in blank

hard

Fill both blanks to collect all prime numbers from the sieve array.

DSA Typescript

const primes = [];
for (let k = 2; k <= n; k++) {
  if (sieve[[1]]) {
    primes.push([2]);
  }
}

Drag options to blanks, or click blank then click option'

Ak

Cn

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using n or i instead of k causes wrong indexing or values.

Checking sieve[n] or sieve[i] is incorrect in this loop.

We check sieve[k] to see if k is prime, then add k to the primes list.

5fill in blank

hard

Fill all three blanks to complete the function that returns all primes up to n.

DSA Typescript

function sieveOfEratosthenes(n: number): number[] {
  const sieve: boolean[] = new Array(n + 1).fill([1]);
  for (let i = 2; i <= [2]; i++) {
    if (sieve[i]) {
      for (let j = i * i; j <= n; j += [3]) {
        sieve[j] = false;
      }
    }
  }
  const primes = [];
  for (let k = 2; k <= n; k++) {
    if (sieve[k]) primes.push(k);
  }
  return primes;
}

Drag options to blanks, or click blank then click option'

Atrue

BMath.sqrt(n)

Ci

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing sieve with false or wrong values.

Looping beyond square root of n wastes time.

Incorrect step size in inner loop causes wrong marking.

The sieve array is initialized with true. The outer loop runs up to the square root of n. The inner loop increments by i to mark multiples as false.

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