Python Prime Number Sieves

The Algorithm

1. Make a table one entry for every number between $\$2\; \backslash leq\{n\}\; \backslash leq\{limit\}\$$
2. Starting at 2, cross out all multiples of 2, not counting 2 itself.
3. Move up to the next number that hasn’t been crossed out
4. Repeat Step 2-3 up till $\$\backslash sqrt\{n\}\$$

Big O Decomposition

The Sieve of Eratosthenes algorithm is a time efficient algorithm.

Time Complexity

A tradeoff for time however is being made for space. Unfortunately, this algorithm requires allocating on the order of n values. Since it requires a table of every number to the last integer in memory, the space complexity of sieves generally grows in the order $\$\backslash mathcal\{O\}(n)\$$

Visually we can depict each loop removing values from the list of real numbers until all that is left are the primes.

• As a refinement, it is sufficient to mark the numbers up to $\$\backslash sqrt\{n\}\$$