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,
- List down all the numbers from 1 to n.
- Assume that all numbers are marked as "prime". Starting with 2, run through the list, proceeding in this manner:
- If the number is marked as "prime", mark all its multiples (save for the number itself—multiple of 1) as "not prime".
- Otherwise, if the number has been marked as "not prime", leave it as it is.
- Do this until you finish the list. (Actually, it is safe to do this only up to the square root of n.)
Wikipedia has a pretty accurate article on the matter.
- Download source. Source is written in the Advanced Student module of
PLT Scheme (now known as PLT Racket). I made use of Advanced Student's