Open Source Your Knowledge, Become a Contributor
Technology knowledge has to be shared and made accessible for free. Join the movement.
- Make a table one entry for every number between 2≤n≤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 √
Big O Decomposition
Sieve of Eratosthenes algorithm is a time efficient algorithm.
A tradeoff for time however is being made for space.
Unfortunately, this algorithm requires allocating on the order of
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)
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 √