This article explains how to determine whether a number is prime, focusing on two efficient seiving algorithms.

Sieve of Eratosthenes

Before learning the Sieve of Eratosthenes, consider the naive trial division method for checking primality of each number:

Naive Method

#include <stdio.h>

int main() {
    int st[100] = {0}; // 0 means prime, 1 means composite
    int n = 100;
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= i / j; j++) {
            if (i % j == 0) {
                st[i] = 1; // mark as composite
            }
        }
    }
}

This method is very slow. We can improve by using the idea: a multiple of a prime is composite. So if P is prime, we can eliminate all multiples of P in the range 2 to 100.

Consider numbers 1 to 11:

First sieve multiples of 2:

Then sieve multiples of 3:

Then sieve multiples of 5:

Now all composites from 1 to 11 are removed. Primes are: 2, 3, 5, 7, 11.

Why does this work? Every composite can be expressed as a product of prime powers, and the composite has a prime factor smaller than itself. By sieving multiples of each prime in increasing order, each composite is eliminated when we reach its smallest prime factor.

Basic Sieve of Eratosthenes

#include <stdio.h>

int main() {
    int n = 100;
    int st[100] = {0};
    for (int i = 2; i <= n; i++) {
        if (st[i] == 0) {
            for (int j = 2 * i; j <= n; j += i) {
                st[j] = 1; // j is a multiple of i, mark as composite
            }
        }
    }
}

The time complexity is O(n log log n).

Optimized Sieve of Eratosthenes

We can optimize:

1. Start marking from ii instead of 2i, because smaller multiples (2i, 3i, ... (i-1)*i) have already been marked by smaller primes.
2. We only need to check primes up to sqrt(n), because any composite has a prime factor ≤ sqrt(n).

#include <stdio.h>
#include <math.h>

int main() {
    int n = 100;
    int st[100] = {0};
    for (int i = 2; i <= (int)sqrt(n); i++) {
        if (st[i] == 0) {
            for (int j = i * i; j <= n; j += i) {
                st[j] = 1;
            }
        }
    }
}

After optimization, the time complexity is approximately O(n).

However, we can do even better with Euler's sieve.

Euler's Sieve (Linear Sieve)

Euler's sieve, also known as the linear seive, achieves O(n) time complexity by ensuring that each composite is eliminated exactly once by its smallest prime factor.

#include <stdio.h>
#include <math.h>

int main() {
    int n = 100;
    int st[100]; // 1 indicates prime (initial), later 0 indicates composite
    for (int i = 0; i < 100; i++) {
        st[i] = 1; // initially assume all numbers are prime
    }
    int primes[100]; // list to store primes
    int primeCount = 0;

    for (int i = 2; i <= (int)sqrt(n); i++) {
        if (st[i] == 1) {
            primes[primeCount] = i;
            primeCount++;
        }
        for (int j = 0; j < primeCount; j++) {
            st[primes[j] * i] = 0; // mark composite
            if (i % primes[j] == 0) {
                break; // primes[j] is the smallest prime factor of i; stop to avoid redundant marking
            }
        }
    }
}

The core idea of Euler's sieve is to ensure that each composite is marked only once by its smallest prime factor, making it highly efficient.