Sieve of Eratosthenes Find All Primes in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Sieve of Eratosthenes?

It is a method to find all prime numbers up to a certain limit by repeatedly marking the multiples of each prime number starting from 2.

intermediate

Why do we start marking multiples from the square of the prime number in the Sieve of Eratosthenes?

Because all smaller multiples of that prime have already been marked by smaller primes, so starting from the square avoids redundant work.

beginner

In the Sieve of Eratosthenes, what does a 'true' value in the boolean array represent?

It means the number at that index is currently considered prime (not marked as a multiple of any smaller prime).

intermediate

What is the time complexity of the Sieve of Eratosthenes algorithm?

The time complexity is approximately O(n log log n), which is very efficient for finding primes up to n.

beginner

How does the Sieve of Eratosthenes help in real-life situations?

It helps quickly find prime numbers which are important in cryptography, hashing, and number theory problems.

What is the first prime number used in the Sieve of Eratosthenes?

A 2

B 1

C 0

D 3

2 is the smallest prime number and the starting point for the sieve.

When marking multiples of a prime p, from which number do we start?

A p * 2

B p * p

C p + 1

D 1

We start from p squared because smaller multiples have been marked by smaller primes.

What data structure is commonly used to keep track of prime candidates in the sieve?

A Boolean array

B Linked list

C Stack

D Queue

A boolean array marks whether each number is prime (true) or not (false).

What happens to multiples of a prime number in the sieve?

A They are doubled

B They are marked as prime

C They are ignored

D They are marked as non-prime

Multiples of primes are marked as non-prime to exclude them.

Which of these numbers will remain true (prime) after running the sieve up to 10?

A 4

B 6

C 7

D 9

7 is prime; 4, 6, and 9 are multiples of smaller primes and marked false.

Explain step-by-step how the Sieve of Eratosthenes finds all primes up to a number n.

Think about marking multiples and moving through the list.

Why is the Sieve of Eratosthenes more efficient than checking each number individually for primality?

Consider how marking multiples saves work.

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