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 √n
Big O Decomposition
The 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 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)
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
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.