Sieve of Eratosthenes

To find all primes up to n, don't test each number on its own. Cross out multiples instead:

1. assume every number from 2 to n is prime
2. for each p still marked prime, cross out p², p² + p, p² + 2p, …
3. whatever remains unmarked is prime

Start at p² because smaller multiples of p were already crossed out by smaller primes. The total work is O(n log log n), practically linear.

Trading memory (a boolean array) for time like this is one of the most common optimization patterns.