# Python Prime Number Sieves

sanghan

17.2K views

### Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

## The Algorithm

- Make a table one entry for every number between $2\le n\le limit$
- Starting at 2, cross out all multiples of 2, not counting 2 itself.
- Move up to the next number that hasn’t been crossed out
- 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}(n\mathrm{log}\mathrm{log}n)$$

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}(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 $\sqrt{n}$

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content