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.