Sieve of Eratosthenes Find All Primes in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the sieve array with true values.

DSA C++

bool sieve[n+1];
for (int i = 0; i <= n; i++) {
    sieve[i] = [1];
}

Drag options to blanks, or click blank then click option'

Atrue

B1

C0

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing sieve with false will mark all numbers as non-prime from the start.

The sieve array should be initialized with true to mark all numbers as potentially prime initially.

2fill in blank

medium

Complete the code to start crossing out multiples from the square of the current prime.

DSA C++

for (int j = [1]; j <= n; j += i) {
    sieve[j] = false;
}

Drag options to blanks, or click blank then click option'

Ai * i

Bi + 1

C2 * i

Di - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from 2*i crosses out multiples twice.

Starting from i+1 is incorrect because it may not be a multiple.

Crossing out multiples starts from i squared because smaller multiples were already handled by smaller primes.

3fill in blank

hard

Fix the error in the loop condition to only check up to the square root of n.

DSA C++

for (int i = 2; i <= [1]; i++) {
    if (sieve[i]) {
        // cross out multiples
    }
}

Drag options to blanks, or click blank then click option'

An / 2

Bsqrt(n)

Cn

Dn * n

Attempts:

3 left

💡 Hint

Common Mistakes

Checking up to n is inefficient and unnecessary.

Using n/2 is arbitrary and not optimal.

We only need to check primes up to the square root of n because larger factors are covered by smaller ones.

4fill in blank

hard

Fill both blanks to print all prime numbers after sieve completion.

DSA C++

for (int i = 2; i <= n; i++) {
    if (sieve[[1]]) {
        std::cout << [2] << " ";
    }
}

Drag options to blanks, or click blank then click option'

Ai

Bn

Csieve[i]

Di + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n or i+1 instead of i causes wrong output or errors.

Using sieve[i] as a print value prints true/false instead of the number.

We check sieve[i] to see if i is prime and print i itself.

5fill in blank

hard

Fill all three blanks to complete the sieve function that returns a vector of primes.

DSA C++

std::vector<int> sieveOfEratosthenes(int n) {
    std::vector<int> primes;
    bool sieve[n+1];
    for (int i = 0; i <= n; i++) {
        sieve[i] = [1];
    }
    for (int i = 2; i <= [2]; 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]) {
            primes.push_back([3]);
        }
    }
    return primes;
}

Drag options to blanks, or click blank then click option'

Atrue

Bsqrt(n)

Ci

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing sieve with false causes no primes to be found.

Looping up to n instead of sqrt(n) is inefficient.

Pushing back sieve[i] instead of i adds boolean values.

Initialize sieve with true, loop up to sqrt(n), and add i to primes if sieve[i] is true.

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