Sieve of Eratosthenes Find All Primes in DSA C++

Mental Model

We mark multiples of each prime number as not prime, so only primes remain unmarked.

Analogy: Imagine a list of numbers like a row of boxes. You paint over boxes that are multiples of smaller numbers, leaving only prime boxes unpainted.

Numbers: 2 3 4 5 6 7 8 9 10
Marks:  _ _ X _ X _ X X  X
_ means unmarked (potential prime), X means marked (not prime)

Dry Run Walkthrough

Input: Find all primes up to 10

Goal: Identify all prime numbers from 2 to 10

Step 1: Start with all numbers from 2 to 10 marked as prime (true)

2[T] 3[T] 4[T] 5[T] 6[T] 7[T] 8[T] 9[T] 10[T]

Why: We assume all numbers are prime initially

Step 2: Mark multiples of 2 (except 2) as not prime

2[T] 3[T] 4[F] 5[T] 6[F] 7[T] 8[F] 9[T] 10[F]

Why: Multiples of 2 cannot be prime

Step 3: Move to next unmarked number 3, mark multiples of 3 (except 3) as not prime

2[T] 3[T] 4[F] 5[T] 6[F] 7[T] 8[F] 9[F] 10[F]

Why: Multiples of 3 cannot be prime

Step 4: Next unmarked number is 5, mark multiples of 5 (except 5) as not prime (none in range)

2[T] 3[T] 4[F] 5[T] 6[F] 7[T] 8[F] 9[F] 10[F]

Why: No multiples of 5 to mark within 10

Step 5: Next unmarked number is 7, mark multiples of 7 (except 7) as not prime (none in range)

2[T] 3[T] 4[F] 5[T] 6[F] 7[T] 8[F] 9[F] 10[F]

Why: No multiples of 7 to mark within 10

Result:

Primes are numbers marked true: 2, 3, 5, 7

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> sieve_of_eratosthenes(int n) {
    vector<bool> prime(n + 1, true); // mark all as prime initially
    prime[0] = false; // 0 is not prime
    prime[1] = false; // 1 is not prime

    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            // mark multiples of p as not prime
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }

    vector<int> primes;
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

int main() {
    int n = 10;
    vector<int> primes = sieve_of_eratosthenes(n);
    for (int prime : primes) {
        cout << prime << " ";
    }
    cout << endl;
    return 0;
}

for (int p = 2; p * p <= n; p++) {

iterate over numbers starting from 2 up to sqrt(n) to find primes

if (prime[p]) {

check if current number p is still marked prime

for (int i = p * p; i <= n; i += p) {

mark all multiples of p starting from p squared as not prime

prime[i] = false;

mark multiple i as not prime

for (int i = 2; i <= n; i++) {

collect all numbers still marked prime into result list

Output

2 3 5 7 

Complexity Analysis

Time: O(n log log n) because we mark multiples of primes efficiently up to n

Space: O(n) because we store a boolean array of size n+1

vs Alternative: Naive checking each number for primality is O(n sqrt n), which is slower than sieve

Edge Cases

n = 0 or n = 1

No primes found, returns empty list

DSA C++

prime[0] = false; prime[1] = false;

n = 2

Returns list with only 2 as prime

DSA C++

for (int i = 2; i <= n; i++) { if (prime[i]) primes.push_back(i); }

large n

Algorithm still works efficiently due to marking from p*p

DSA C++

for (int i = p * p; i <= n; i += p) { prime[i] = false; }

When to Use This Pattern

When asked to find all primes up to a number efficiently, use the Sieve of Eratosthenes to mark multiples and quickly identify primes.

Common Mistakes

Mistake: Starting to mark multiples from p*2 instead of p*p
Fix: Start marking from p*p because smaller multiples were already marked by smaller primes

Mistake: Not marking 0 and 1 as not prime
Fix: Explicitly mark prime[0] and prime[1] as false before starting

Summary

Finds all prime numbers up to a given limit by marking multiples of primes as not prime.

Use it when you need a fast way to list all primes up to a number.

The key insight is to start marking multiples from the square of each prime to avoid redundant work.

Practice

1. What is the main purpose of the Sieve of Eratosthenes algorithm?

easy

A. To calculate the factorial of a number

B. To sort an array of numbers

C. To find the greatest common divisor of two numbers

D. To find all prime numbers up to a given limit

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 D

4. Quick Check:

   Sieve finds primes = D [OK]

Hint: Sieve marks multiples to find primes fast [OK]

Common Mistakes:

• Confusing sieve with sorting algorithms
• Thinking it calculates factorial or gcd
• Assuming it finds primes beyond the limit

2. Which of the following C++ code snippets correctly initializes the sieve array for numbers up to n?

easy

A. std::vector<bool> sieve(n+1, true); sieve[0] = sieve[1] = false;

B. std::vector<int> sieve(n, 0); sieve[0] = sieve[1] = 1;

C. bool sieve[n]; for(int i=0; i

D. std::vector<bool> sieve(n+1, false); sieve[0] = sieve[1] = true;

Solution

1. Step 1: Check initialization for prime marking

   The sieve should start with all true except 0 and 1, which are not prime.

2. Step 2: Validate code correctness

   std::vector<bool> sieve(n+1, true); sieve[0] = sieve[1] = false; uses a vector<bool> with size n+1, sets all true, then marks 0 and 1 false correctly.

3. Final Answer:

   std::vector<bool> sieve(n+1, true); sieve[0] = sieve[1] = false; -> Option A

4. Quick Check:

   Initialize sieve true except 0,1 false = A [OK]

Hint: Start sieve with true, mark 0 and 1 false [OK]

Common Mistakes:

• Using wrong data type for sieve array
• Not marking 0 and 1 as non-prime
• Initializing all false instead of true

3. What will be the output primes printed by the following C++ code snippet using Sieve of Eratosthenes for n = 10?

int n = 10;
std::vector<bool> sieve(n+1, true);
sieve[0] = sieve[1] = false;
for (int i = 2; i * i <= n; i++) {
  if (sieve[i]) {
    for (int j = i * i; j <= n; j += i) {
      sieve[j] = false;
    }
  }
}
for (int i = 2; i <= n; i++) {
  if (sieve[i]) std::cout << i << " ";
}

medium

A. 2 3 4 5 7

B. 2 3 5 7

C. 1 2 3 5 7

D. 2 3 5 7 9

Solution

1. Step 1: Run sieve marking multiples

   Multiples of 2 (4,6,8,10) and 3 (9) are marked false.

2. Step 2: Identify primes left true

   Numbers 2, 3, 5, 7 remain true and are printed.

3. Final Answer:

   2 3 5 7 -> Option B

4. Quick Check:

   Primes up to 10 = 2 3 5 7 [OK]

Hint: Mark multiples starting from i*i to avoid repeats [OK]

Common Mistakes:

• Including non-primes like 4 or 9
• Printing 1 as prime
• Not starting inner loop from i*i

4. Identify the error in the following Sieve of Eratosthenes code snippet and select the fix:

int n = 20;
std::vector<bool> sieve(n+1, true);
sieve[0] = sieve[1] = false;
for (int i = 2; i <= n; i++) {
  if (sieve[i]) {
    for (int j = i * 2; j <= n; j += i) {
      sieve[j] = false;
    }
  }
}

medium

A. Start inner loop from j = i + 1

B. Initialize sieve with false instead of true

C. Change outer loop condition to i * i <= n

D. Remove sieve[0] and sieve[1] assignments

Solution

1. Step 1: Analyze loop conditions

   The outer loop runs up to n, which is inefficient and unnecessary.

2. Step 2: Correct loop to optimize marking

   Changing outer loop to run while i * i <= n avoids redundant checks and improves performance.

3. Final Answer:

   Change outer loop condition to i * i <= n -> Option C

4. Quick Check:

   Outer loop limit = i*i <= n [OK]

Hint: Outer loop runs till i*i <= n for efficiency [OK]

Common Mistakes:

• Running outer loop till n wastes time
• Starting inner loop incorrectly
• Not marking 0 and 1 false

5. You want to find all prime numbers up to n = 50 using the Sieve of Eratosthenes. After running the sieve, how many primes will be found?

hard

A. 15

B. 16

C. 14

D. 17

Solution

1. Step 1: List primes up to 50

   Primes are: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 (total 15).

2. Step 2: Count primes correctly

   Counting carefully confirms total primes up to 50 is 15.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Count primes ≤ 50 = 15 [OK]

Hint: Count primes carefully or use sieve output count [OK]

Common Mistakes:

• Counting non-primes like 1 or 9
• Including primes beyond 50
• Miscounting total primes