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.

Create Content

The Algorithm

  1. Make a table one entry for every number between 2nlimit
  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 n

Animation

Big O Decomposition

The Sieve of Eratosthenes algorithm is a time efficient algorithm.

Time Complexity

O(nloglogn)

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.

Sieve

  • As a refinement, it is sufficient to mark the numbers up to n
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content