Number Theory for Competitive Programming

A sieve that computes smallest prime factors (or primality) for all n ≤ N in O(N) time by ensuring every composite is marked exactly once: it is struck out by its smallest prime factor. The break condition `if p divides i` prevents double marking.

For each i, iterate over collected primes p and mark i·p. The loop breaks as soon as p divides i, guaranteeing p is the smallest prime factor of i·p so each composite is hit only by its minimal prime.

Marking multiples of each prime p from p² up to N gives total work ∑ N/p over primes p ≤ N, which is O(N log log N) by Mertens' theorem.

To find primes in a high range [L, R] without storing all of [0, R], precompute primes up to √R, then mark composites within the block [L, R] using those primes. Memory is O(√R + (R − L)).

The segmented sieve processes a window [L, R] at a time, so it needs only O(√R) storage for base primes plus O(R − L) for the current block, enabling sieving near 10^12 where a full sieve is infeasible.

Modular arithmetic distributes over + and ·: (a + b) mod m = ((a mod m) + (b mod m)) mod m, and likewise for products. Reduce operands before and after to avoid overflow.