Sieve of Eratosthenes Find All Primes in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sieve for n=10

What is the output of the following C++ code that uses the Sieve of Eratosthenes to find primes up to 10?

DSA C++

#include <iostream>
#include <vector>

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

A 2 3 5 7

B 2 3 4 5 7

C 2 3 5 7 9

D 1 2 3 5 7

💡 Hint

Remember that 1 is not a prime number and multiples of primes are marked false.

The Sieve marks multiples of each prime starting from its square as not prime. For n=10, primes are 2, 3, 5, and 7.

🧠 Conceptual

intermediate

Why start marking multiples from p*p?

In the Sieve of Eratosthenes, why do we start marking multiples of a prime p from p*p instead of 2*p?

A Because starting from 2*p causes runtime errors.

B Because p*p is the smallest prime number.

C Because 2*p is not a multiple of p.

D Because all smaller multiples of p are already marked by smaller primes.

💡 Hint

Think about when multiples get marked in earlier steps.

Multiples less than p*p are already marked by smaller primes, so starting at p*p avoids redundant work.

🔧 Debug

advanced

Identify the error in this sieve code

What error will this code produce when run for n=10?

DSA C++

#include <iostream>
#include <vector>

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

A Compilation error: cannot assign to prime[0]

B Outputs primes correctly: 2 3 5 7

C Runtime error: out_of_range exception

D Outputs: 2 3 4 5 7

💡 Hint

Check the size of the vector and the indices accessed.

The vector size is n=10, so valid indices are 0 to 9. Accessing prime[10] causes out_of_range error.

❓ Predict Output

advanced

Output of Sieve for n=20 with print of primes count

What is the output of this code that prints all primes up to 20 and then prints the count of primes found?

DSA C++

#include <iostream>
#include <vector>

int main() {
    int n = 20;
    std::vector<bool> prime(n+1, true);
    prime[0] = prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            std::cout << i << " ";
            count++;
        }
    }
    std::cout << "\nCount: " << count << std::endl;
    return 0;
}

A

2 3 5 7 11 13 17 19 
Count: 8

B

2 3 5 7 11 13 17 19 20 
Count: 9

C

2 3 5 7 9 11 13 17 19 
Count: 9

D

2 3 5 7 11 13 15 17 19 
Count: 9

💡 Hint

Remember that 9, 15, and 20 are not primes.

The primes up to 20 are 2, 3, 5, 7, 11, 13, 17, and 19. Count is 8.

🧠 Conceptual

expert

Time complexity of Sieve of Eratosthenes

What is the time complexity of the Sieve of Eratosthenes algorithm for finding all primes up to n?

A O(n^2)

B O(n log log n)

C O(n log n)

D O(sqrt(n))

💡 Hint

The sieve is faster than n log n but slower than linear.

The Sieve of Eratosthenes runs in O(n log log n) time, which is very efficient for prime generation.

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