Bird
Raised Fist0
DSA Typescriptprogramming~5 mins

Sieve of Eratosthenes Find All Primes in DSA Typescript - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Sieve of Eratosthenes Find All Primes
O(n log log n)
Understanding Time Complexity

We want to understand how the time needed to find all prime numbers grows as the input number gets bigger.

Specifically, how does the Sieve of Eratosthenes perform when finding primes up to a number n?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


function sieveOfEratosthenes(n: number): boolean[] {
  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;
      }
    }
  }
  return primes;
}

This code marks non-prime numbers as false, leaving primes marked true up to n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: The nested loops where multiples of each prime candidate are marked false.
  • How many times: The outer loop runs roughly up to the square root of n, and the inner loop marks multiples starting from i² up to n.
How Execution Grows With Input

As n grows, the number of operations grows a bit faster than n but less than n squared.

Input Size (n)Approx. Operations
10~20
100~500
1000~8,000

Pattern observation: The operations grow roughly proportional to n times the logarithm of the logarithm of n, which grows slowly compared to n².

Final Time Complexity

Time Complexity: O(n log log n)

This means the time grows a bit faster than n but much slower than n squared, making it efficient for large n.

Common Mistake

[X] Wrong: "The algorithm checks every number against all others, so it must be O(n²)."

[OK] Correct: The inner loop skips many numbers by jumping in steps of i, and the outer loop only goes up to √n, so it does far fewer checks than n².

Interview Connect

Understanding this time complexity helps you explain why the sieve is a smart way to find primes quickly, showing your grasp of efficient algorithms.

Self-Check

"What if we started marking multiples from 2*i instead of i*i? How would the time complexity change?"

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard