Sieve of Eratosthenes Find All Primes in DSA C - Build from Scratch

Sieve of Eratosthenes Find All Primes

📖 Scenario: You are helping a teacher prepare a list of prime numbers for a math class. The teacher wants to find all prime numbers up to a certain number using a fast method called the Sieve of Eratosthenes.

🎯 Goal: Build a program that finds and prints all prime numbers up to a given number using the Sieve of Eratosthenes method.

📋 What You'll Learn

Create an array to mark numbers as prime or not

Use a variable to store the maximum number to check

Implement the sieve algorithm to mark non-prime numbers

Print all prime numbers found

💡 Why This Matters

🌍 Real World

Finding prime numbers quickly is useful in cryptography, computer security, and math research.

💼 Career

Understanding prime number algorithms helps in software development roles involving security, algorithms, and performance optimization.

1

Create the array to mark primes

Create an integer array called is_prime of size 21 to mark numbers from 0 to 20. Initialize all elements to 1 except for index 0 and 1, which should be set to 0 because 0 and 1 are not prime.

DSA C

int is_prime[21];
// Your code here

Hint

Use a for loop from 0 to 20. Set is_prime[0] and is_prime[1] to 0, others to 1.

2

Set the maximum number to check

Create an integer variable called max_num and set it to 20. This will be the highest number we want to check for primes.

DSA C

int is_prime[21];

for (int i = 0; i <= 20; i++) {
    if (i == 0 || i == 1) {
        is_prime[i] = 0;
    } else {
        is_prime[i] = 1;
    }
}

// Your code here

Hint

Just create int max_num = 20;

3

Implement the sieve algorithm

Use a for loop with variable i from 2 while i * i <= max_num. Inside it, if is_prime[i] is 1, use another for loop with variable j starting from i * i to max_num, incrementing by i. Set is_prime[j] to 0 inside the inner loop to mark multiples as not prime.

DSA C

int is_prime[21];

for (int i = 0; i <= 20; i++) {
    if (i == 0 || i == 1) {
        is_prime[i] = 0;
    } else {
        is_prime[i] = 1;
    }
}

int max_num = 20;

// Your code here

Hint

Use nested loops: outer from 2 to sqrt(max_num), inner from i*i to max_num stepping by i.

4

Print all prime numbers

Use a for loop with variable i from 2 to max_num. Inside the loop, if is_prime[i] is 1, print i followed by a space. After the loop, print a newline character.

DSA C

int is_prime[21];

for (int i = 0; i <= 20; i++) {
    if (i == 0 || i == 1) {
        is_prime[i] = 0;
    } else {
        is_prime[i] = 1;
    }
}

int max_num = 20;

for (int i = 2; i * i <= max_num; i++) {
    if (is_prime[i] == 1) {
        for (int j = i * i; j <= max_num; j += i) {
            is_prime[j] = 0;
        }
    }
}

// Your code here

Hint

Print all numbers where is_prime[i] is 1, separated by spaces, then print a newline.