Sieve of Eratosthenes

Tags: algorithm

Is an algorithm for quickly finding all the prime-numbers up-to any given limit.

The sieve works by filling a pad of all the numbers up-to the limit $n$ . We then scratch off the first number as prime and then mark-off all of its multiples as non-prime (because their factors of the last marked prime number). Then we scratch off the next non-marked number as prime and repeat the process.

Figure 1: Figure showing the sieve of eratorthenes in action.