Why Sieve of Eratosthenes Find All Primes in DSA C++?

The Big Idea

Discover how a simple marking trick can find all primes faster than checking each number one by one!

The Scenario

Imagine you want to find all prime numbers up to 100 by checking each number one by one, dividing it by all smaller numbers to see if it has any divisors.

The Problem

This manual method is very slow and tiring because you have to do many repeated checks. It's easy to make mistakes and miss some primes or waste time checking numbers unnecessarily.

The Solution

The Sieve of Eratosthenes quickly marks off multiples of each prime starting from 2, so you only check each number once. This way, you find all primes efficiently without repeated work.

Before vs After

✗ Before

for (int num = 2; num <= 100; num++) {
  bool isPrime = true;
  for (int div = 2; div < num; div++) {
    if (num % div == 0) {
      isPrime = false;
      break;
    }
  }
  if (isPrime) cout << num << " ";
}

✓ After

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

What It Enables

This method lets you find all prime numbers up to a large limit quickly and easily, saving time and avoiding errors.

Real Life Example

When encrypting messages securely, computers need to find large prime numbers fast. The sieve helps generate these primes efficiently.

Key Takeaways

Manual prime checking is slow and repetitive.

Sieve of Eratosthenes marks multiples to find primes efficiently.

It enables fast prime generation for many applications.

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