## 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.

## Downloads

- 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`vector`

data structure.