Why it matters

Prime generation appears everywhere from crypto to Project Euler. Understanding sieve is standard.

Advertisement

The architecture

Array of size N, initially all true.

For each prime p (starting 2): mark p², p²+p, ..., as composite.

Remaining true positions are prime.

Sieve algorithmInit arrayall candidatesFor each prime pmark multiplesRemainingare primesOnly mark from p²; smaller composites of p already marked by smaller primes
Sieve mechanics.
Advertisement

How it works end to end

Complexity: O(n log log n). Nearly linear.

Linear sieve: variant that generates each composite once. Truly O(n).

Segmented sieve: for very large N, work in segments to fit in cache.

Applications: prime factorization tables, prime testing precomputation, Euler's totient function.