Why Sieve of Eratosthenes Find All Primes in DSA Python?

The Big Idea

What if you could find all primes up to 100 in seconds instead of minutes of tedious checking?

The Scenario

Imagine you want to find all prime numbers up to 100 by checking each number one by one and testing if it is divisible by any smaller number.

This means lots of repeated division and slow work.

The Problem

Checking each number manually takes a long time because you test many unnecessary divisions.

It is easy to make mistakes and miss some primes or mark some wrong.

This slow and error-prone method wastes time and effort.

The Solution

The Sieve of Eratosthenes quickly finds all primes by marking multiples of each prime as not prime.

This way, you avoid repeated checks and get all primes efficiently.

Before vs After

✗ Before

for num in range(2, 101):
    is_prime = True
    for div in range(2, num):
        if num % div == 0:
            is_prime = False
            break
    if is_prime:
        print(num)

✓ After

limit = 100
prime = [True] * (limit + 1)
prime[0], prime[1] = False, False
for number in range(2, int(limit**0.5) + 1):
    if prime[number]:
        for multiple in range(number*number, limit + 1, number):
            prime[multiple] = False
for i in range(2, limit + 1):
    if prime[i]:
        print(i)

What It Enables

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

Real Life Example

Finding prime numbers fast helps in cryptography, where secure keys depend on large primes.

Key Takeaways

Manual prime checking is slow and error-prone.

Sieve of Eratosthenes marks multiples to find primes efficiently.

This method is fast, simple, and useful for many applications.