The Sieve of Eratosthenes finds all primes up to n efficiently. Instead of testing each number individually, it eliminates composites in batches.
The idea: start with all numbers from 2 to n. Mark 2 as prime, then cross out all multiples of 2. Mark 3 as prime, cross out all multiples of 3. Continue until you reach √n.
All numbers that remain unmarked are prime. This works because every composite has a prime factor ≤ √n.