How do you actually find the primes up to some limit? Eratosthenes, the librarian of Alexandria, gave the answer around 200 BC, and it is still the fastest simple method known. The idea is to find primes not by testing each number, but by striking out every number that isn't one — sieving the composites away until only primes remain.

The method

1. Write the numbers 2, 3, 4, \dots, N.
2. Circle the first un-struck number — it is prime. Strike out all of its larger multiples.
3. Repeat with the next un-struck number, and so on.

Whatever survives is prime. The one shortcut worth knowing: you can stop once you reach \sqrt{N}. Any composite n \le N has a factor no bigger than \sqrt{n} \le \sqrt{N}, so it has already been struck by then. Step through it below.

Why it works

Every composite number has a smallest prime factor p, and the sieve strikes it out exactly when it processes that p. So no composite can survive. A prime, on the other hand, is a multiple of no smaller number, so nothing ever strikes it. The sieve is just the Fundamental Theorem of Arithmetic in action — every composite betrayed by its smallest prime factor.