Sieve of Eratosthenes (in Python)
The goal is to find all the prime numbers less than or equal to some natural number maxn.
We have a list that tells us if any of the numbers 0..maxn are "marked". It can be an array of booleans. The zero and one slots are not used.
Start with 2 and mark all the multiples of 2.
Find the next unmarked number d, mark all of its multiples, and so on.
You can stop when 2d>maxn, or there are no more unmarked numbers.
To print out the primes, print out all unmarked numbers.