Scheme: Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient technique (attributed to Eratosthenes, yes) for finding all prime numbers less than or equal to a given number n. It runs in O(n log log n) time but, after the initial overhead, you can check for the primality of any number in O(1) time.

A rough sketch of how it works is as follows,

Wikipedia has a pretty accurate article on the matter.

Downloads