Why Sieve of Eratosthenes Find All Primes in DSA C?

The Big Idea

Discover how a simple marking trick can find 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 every smaller number 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 unnecessary numbers.

The Solution

The Sieve of Eratosthenes quickly marks off multiples of each prime number starting from 2, so you don't have to check every number individually. It efficiently finds all primes up to your limit with fewer steps.

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) printf("%d ", num);
}

✓ After

bool isPrime[101];
for (int i = 2; i <= 100; i++) isPrime[i] = true;
for (int i = 2; i * i <= 100; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= 100; j += i) isPrime[j] = false;
    }
}
for (int i = 2; i <= 100; i++) {
    if (isPrime[i]) printf("%d ", i);
}

What It Enables

This method enables you to find all prime numbers up to any large number quickly and reliably.

Real Life Example

Finding prime numbers fast is useful in cryptography, where secure keys depend on large prime numbers.

Key Takeaways

Manual prime checking is slow and error-prone.

Sieve of Eratosthenes marks multiples to find primes efficiently.

It helps find all primes up to a limit quickly.