# Python Prime Number Sieves

sanghan
3,210 views

## The Algorithm

1. Make a table one entry for every number between $2\le n\le 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 $\sqrt{n}$

### Big O Decomposition

The Sieve of Eratosthenes algorithm is a time efficient algorithm.

#### Time Complexity

$\mathcal{O}\left(n\mathrm{log}\mathrm{log}n\right)$

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 $\mathcal{O}\left(n\right)$

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 $\sqrt{n}$
Open Source Your Knowledge: become a Contributor and help others learn.