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 list of primes printed by this Sieve of Eratosthenes code for n=10?

DSA C

int n = 10;
int primes[10];
for(int i = 0; i < n; i++) primes[i] = 1;
primes[0] = 0; primes[1] = 0;
for(int i = 2; i*i < n; i++) {
    if(primes[i]) {
        for(int j = i*i; j < n; j += i) primes[j] = 0;
    }
}
for(int i = 2; i < n; i++) {
    if(primes[i]) printf("%d ", i);
}

A [2, 3, 5, 6, 7]

B [2, 3, 4, 5, 7]

C [2, 3, 5, 7, 9]

D [2, 3, 5, 7]

💡 Hint

Remember that the sieve marks multiples of primes as not prime.

The sieve marks 4, 6, 8, 9, 10 as not prime. Only 2, 3, 5, 7 remain.

❓ Predict Output

intermediate

Count of primes up to 20

How many primes does the Sieve of Eratosthenes find up to n=20?

DSA C

int n = 20;
int primes[20];
for(int i = 0; i < n; i++) primes[i] = 1;
primes[0] = 0; primes[1] = 0;
for(int i = 2; i*i < n; i++) {
    if(primes[i]) {
        for(int j = i*i; j < n; j += i) primes[j] = 0;
    }
}
int count = 0;
for(int i = 2; i < n; i++) {
    if(primes[i]) count++;
}
printf("%d", count);

A 8

B 9

C 7

D 10

💡 Hint

Count primes: 2,3,5,7,11,13,17,19

There are 8 primes less than 20: 2,3,5,7,11,13,17,19.

🔧 Debug

advanced

Identify the error in Sieve implementation

What error does this Sieve of Eratosthenes code produce when run for n=15?

DSA C

int n = 15;
int primes[15];
for(int i = 0; i < n; i++) primes[i] = 1;
primes[0] = 0; primes[1] = 0;
for(int i = 2; i*i < n; i++) {
    if(primes[i]) {
        for(int j = i*i; j < n; j += i) primes[j] = 0;
    }
}
for(int i = 2; i < n; i++) {
    if(primes[i]) printf("%d ", i);
}

A Array index out of bounds error

B Compilation error due to missing semicolon

C No error, prints primes correctly

D Infinite loop

💡 Hint

Check the loop that initializes the primes array.

The loop runs from i=0 to i<=n which accesses primes[n], out of bounds for array size n.

❓ Predict Output

advanced

Output of Sieve for n=30 with print format

What is the printed output of primes for n=30 using this code?

DSA C

int n = 30;
int primes[30];
for(int i = 0; i < n; i++) primes[i] = 1;
primes[0] = 0; primes[1] = 0;
for(int i = 2; i*i < n; i++) {
    if(primes[i]) {
        for(int j = i*i; j < n; j += i) primes[j] = 0;
    }
}
for(int i = 2; i < n; i++) {
    if(primes[i]) printf("%d->", i);
}
printf("null");

A 2->3->5->7->11->13->17->19->23->29->null

B 2->3->5->7->9->11->13->17->19->23->29->null

C 2->3->5->7->11->13->17->19->23->27->null

D 2->3->5->7->11->13->17->19->23->29

💡 Hint

Remember 9 and 27 are not primes.

The sieve removes multiples of primes, so 9 and 27 are excluded.

🧠 Conceptual

expert

Why does the inner loop start at i*i in Sieve?

In the Sieve of Eratosthenes, why does the inner loop start marking multiples from i*i instead of 2*i?

A Because i*i is the smallest prime number

B Because all smaller multiples of i were already marked by smaller primes

C Because starting at 2*i would miss some primes

D Because starting at i*i reduces memory usage

💡 Hint

Think about when multiples less than i*i get marked.

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