Sieve of Eratosthenes Time and Space Complexity

In the previous article, we learned about what is sieve of Eratosthenes algorithm and how to implement it in java.

in this article, we are going to learn about the time and space complexity of sieve of the Eratosthenes algorithm.

Let us take an example when n = 50. So we need to print all prime numbers smaller than or equal to 50.

We create a table of all numbers from 2 to 50.

It involves methodically eliminating the numbers known not to be prime until only the prime numbers remain. Begin by crossing out 1 as it is not a prime number (it does not have two factors, it is a square number).

2 is a prime number but all of its multiples a not (they are composite numbers) so cross out all of the multiples of 2 but leave 2 as the first prime number.

Next, cross out all of the multiples of 3 except 3 itself.

The number 4 and all of its multiples have already been crossed out as they are also multiples of 2.

Next, cross out all the multiples of 5 except 5 itself.

Continue this process until you have discovered as many prime numbers as you need.

at first, we are eliminating all the numbers that are multiples of 2 and how many numbers multiple of 2 exist in the range till n ---> n/2

same goes for 3:--

we are eliminating all the numbers that are multiples of 3 and how many numbers multiple of 3 exist in the range till n ---> n/3

same for 5, 7 ......

the first time the loop is running for 2, now mark all the multiple of 2 as not prime. ok

same for 3, 5, 7 ......

So, Time Complexity:-

n/2 + n/3 + n/5 + n/7 + ..........

taking n common

n(1/2 + 1/3 + 1/5 + 1/7 + .........)

so the expression__

(1/2 + 1/3 + 1/5 + 1/7 + .........)

Proof of Harmonic Progression of the sum of primes: In order to understand the proof, the prerequisite is the harmonic serise and Taylor series expansion.
- Lets take an the equation:
  
  $log(\frac{x}{1 - x})$
- The taylor series expansion of the above equation is given by:
  
  $x + \frac{x^2}{2} + \frac{x^3}{3} + ...$
- Putting x = 1 in the above equation, we get the relation:
  
  $\sum_1^n \frac{1}{r} = log(n)$
  
  Let’s mark the above equation as 1.
- From Euler’s product formula,
  
  $\sum_1^\infty \frac{1}{r^{s}} = \prod \frac{1}{1 - p^{-s}}$
- On substituting s = 1 in the above equation, we get
  
  $\sum_1^\infty \frac{1}{r^{1}} = \prod \frac{1}{1 - p^{-1}}$
- On applying log to both the sides:
  
  $log(\sum_1^\infty \frac{1}{r^{1}}) = log(\prod \frac{1}{1 - p^{-1}})$
- On simplifying the above equation, it becomes:
  
  $log(\sum_1^\infty \frac{1}{r^{1}}) = \sum log( \frac{1}{1 - p^{-1}})$
- In the above equation, 1 > p^-1 > -1
- Thus, we can use taylor series expansion for the right hand side of the above equation.
  
  $log( \frac{1}{1-x}) = \sum_1^\infty log( \frac{1}{n * p^{n}})$
- On substituting this in the above equation, we get:
  
  $log( \sum_1^n \frac{1}{r}) = \sum \sum_1^n \frac{1}{n * p^{n}}$
  
  where p is a prime number.
- On expanding the inner summation;
  
  $\sum_1^n \frac{1}{n * p^{n}} = \frac{1}{p} + \frac{1}{2p^{2}} + \frac{1}{3p^{2}} + .....$
- The above series is convergent. So, the above series can be approximated to:
  
  $\frac{1}{p}$
- Therefore, on substituting and rewriting the equation; we get
  
  $log( \sum_1^\infty \frac{1}{n}) = \sum \frac{1}{p}$
  
  where p is the prime number.
- From the initial equation 1, we can finally conclude that:
  
  $\sum \frac{1}{p} = log(log(n))$
  
  where p is the sum of prime numbers.