Hello everyone.

Recently I learned the Sieve of Eratosthenes, and it was one of the most interesting algorithms I have encountered in competitive programming so far.

At first, I used to check whether a number is prime using trial division.

bool isPrime(int n){
    if(n < 2) return false;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}

The complexity is approximately O(√N).

For a single query, this is fine.

But what if we need to determine prime numbers from 1 to 1,000,000?

Doing primality testing separately for every number becomes expensive.

Then I discovered the Sieve of Eratosthenes.

The main idea is surprisingly simple:

• Assume every number is prime.
• Start from 2.
• Mark all multiples of 2 as composite.
• Move to the next unmarked number.
• Mark all of its multiples.
• Continue.

const int N = 1000000;
vector<bool> prime(N + 1, true);

prime[0] = prime[1] = false;

for(int i = 2; i * i <= N; i++){
    if(prime[i]){
        for(int j = i * i; j <= N; j += i){
            prime[j] = false;
        }
    }
}

The most surprising part for me was the complexity.

Trial Division:

• O(N√N) for all numbers

Sieve:

• O(N log log N)

For N = 1,000,000 the difference is massive.

What I learned:

1. Smart preprocessing can be more important than brute force checking.
2. Mathematics can dramatically reduce complexity.
3. Competitive programming is often about finding a better approach rather than writing faster code.

After learning Sieve, I became much more interested in Number Theory.

My next targets are:

• Prime Factorization
• Smallest Prime Factor (SPF)
• Segmented Sieve
• Euler's Totient Function

If you have any advice or resources for learning Number Theory, I would love to hear them.

Thanks for reading.