# Python Prime Number Sieves

sanghan

1,819 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≤n≤limit$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 √n$\sqrt{n}$

### Big O Decomposition

The `Sieve of Eratosthenes`

algorithm is a time efficient algorithm.

#### Time Complexity

O(nloglogn)$\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 O(n)$\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 √n$\sqrt{n}$

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