One of the earliest algorithms ever invented. Eratosthenes found a quick way to find all the primes up to a given number n.

Start with the numbers 2,3,...,n. Repeatedly remove all the multiples of the first number in the list, except that number. The first time round, that's 2, so strike 4,6,8... Then the first number is 3, so you strike 6,9,12,... (Note that 6 is already out, from the first stage -- that's OK). Stop when the square of the first number in the list is greater than n. That's it. You can code this pretty efficiently with various tricks of the trade, but the principle is the same.

Obviously, we only delete numbers from the list which **are not** prime (they're all non-trivial multiples of some number). On the other hand, any composite number up to n is necessarily deleted at some point: such a number may be written xy, and either x^{2}<=n or y^{2}<=n (otherwise xy>n). So the list we end up with is exactly the primes up to n.