Codility - Lesson 11 Sieve of Eratosthenes

Source Link:
https://codility.com/programmers/lessons/11-sieve_of_eratosthenes/

Wikipedia:
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes



Some notes: 
The Sieve of Eratosthenes is a very simple and popular technique for finding all the prime
numbers in the range from 2 to a given number n.

It is sufficient to remove only multiples of prime numbers not exceeding (n)^(1/2).

 

The above illustration shows steps of sieving for n = 17.
First, we remove multiples of the smallest element in the set, which is 2. 
The next element remaining in the set is 3, and we also remove its multiples, and so on.

11.1: Sieve of Eratosthenes.
1 def sieve(n):
2 sieve = [True] * (n + 1)
3 sieve[0] = sieve[1] = False
4 i = 2
5 while (i * i <= n):
6 if (sieve[i]):
7 k = i * i
8 while (k <= n):
9 sieve[k] = False
10 k += i
11 i += 1
12 return sieve

So the overall time complexity of this algorithm is O(n log log n).