Python sieve of eratosthenes

Sieve of Eratosthenes Algorithm: Python, C++ Example

The Sieve of Eratosthenes is the simplest prime number sieve. It is a Prime number algorithm to search all the prime numbers in a given limit. There are several prime number sieves. For example- the Sieve of Eratosthenes, Sieve of Atkin, Sieve of Sundaram, etc.

The word “sieve” means a utensil that filters substances. Thus, the sieve algorithm in Python and other languages refers to an algorithm to filter out prime numbers.

This algorithm filters out the prime number in an iterative approach. The filtering process starts with the smallest prime number. A Prime is a natural number that is greater than 1 and has only two divisors, viz., 1 and the number itself. The numbers that are not primes are called composite numbers.

In the sieve of the Eratosthenes method, a small prime number is selected first, and all the multiples of it get filtered out. The process runs on a loop in a given range.

For example:

Let’s take the number range from 2 to 10.

After applying the Sieve of Eratosthenes, it will produce the list of prime numbers 2, 3, 5, 7

Algorithm Sieve of Eratosthenes

Here is the algorithm for the Sieve of Eratosthenes:

Step 1) Create a list of numbers from 2 to the given range n. We start with 2 as it is the smallest and first prime number.

Step 2) Select the smallest number on the list, x (initially x equals 2), traverse through the list, and filter the corresponding composite numbers by marking all the multiples of the selected numbers.

Step 3) Then choose the next prime or the smallest unmarked number on the list and repeat step 2.

Step 4) Repeat the previous step until the value of x should be lesser than or equal to the square root of n (x

Note: The mathematical reasoning is quite simple. The number range n can be factorized as-

Again, n = *

= (factor smaller than ) * (factor larger than )

So at least one of the prime factors or both must be

Step 5) After those four steps, the remaining unmarked numbers would be all the primes on that given range n.

Let’s take an example and see how it works.

For this example, we will find the list of prime numbers from 2 to 25. So, n=25.

Step 1) In the first step, we will take a list of numbers from 2 to 25 as we selected n=25.

Step 2) Then we select the smallest number on the list, x. Initially x=2 as it is the smallest prime number. Then we traverse through the list and mark the multiples of 2.

The multiples of 2 for the given value of n is: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Note: Blue color denotes the selected number, and pink color denotes the eliminated multiples

Step 3) Then we choose the next smallest unmarked number, which is 3, and repeat the last step by marking the multiples of 3.

Step 4) We repeat step 3 in the same way until x= or 5.

Step 5) The remaining non-marked numbers would be the prime numbers from 2 to 25.

Pseudo-Code

Begin Declare a boolean array of size n and initialize it to true For all numbers i : from 2 to sqrt(n) IF bool value of i is true THEN i is prime For all multiples of i (i
Sieve of Eratosthenes C/C++ code Example
#include #include using namespace std; void Sieve_Of_Eratosthenes(int n) < // Create and initialize a boolean array bool primeNumber[n + 1]; memset(primeNumber, true, sizeof(primeNumber)); for (int j = 2; j * j > for (int i = 2; i int main()
Sieve of Eratosthenes Python Program Example
def SieveOfEratosthenes(n): # Create a boolean array primeNumber = [True for i in range(n+2)] i = 2 while (i * i 
Segmented Sieve
We have seen that the Sieve of Eratosthenes is required to run a loop through the whole number range. Thus, it needs O(n) memory space to store the numbers. The situation becomes complicated when we try to find primes in a huge range. It is not feasible to allocate such a large memory space for a bigger n.
The algorithm can be optimized by introducing some new features. The idea is to divide the number range into smaller segments and compute prime numbers in those segments one by one. This is an efficient way to reduce space complexity. This method is called a segmented sieve.
The optimization can be achieved in the following manner:

  
Use a simple sieve to find prime numbers from 2 to  and store them in an array.
  
Divide the range [0…n-1] into multiple segments of size at most  .
  
For every segment, iterate through the segment and mark the multiple of prime numbers found in step 1. This step requires O( ) at max.


The regular sieve requires O(n) auxiliary memory space, whereas the segmented sieve requires O( ), which is a big improvement for a large n. The method has a downside also because it does not improve time complexity.
Complexity Analysis
Space Complexity: 
The simple sieve of eratosthenes algorithm requires O(n) memory space. And the segmented sieve requires 
O( ) auxiliary space.
Time Complexity:
The time complexity of a regular sieve of eratosthenes algorithm is O(n*log(log(n))). The reasoning behind this complexity is discussed below.
For a given number n, the time required to mark a composite number (i.e., nonprime numbers) is constant. So, the number of times the loop runs is equal to-
The harmonic progression of the sum of the primes can be deducted as log(log(n)).
So, the time complexity will be-
Thus the time complexity O(n * log(log(n)))

  
The Sieve of Eratosthenes filter out the prime numbers in a given upper limit.
  
Filtering a prime number starts from the smallest prime number, “2”. This is done iteratively.
  
The iteration is done up to the square root of n, where n is the given number range.
  
After these iterations, the numbers that remain are the prime numbers.
Источник
Sieve of Eratosthenes: Finding All Prime Numbers

Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
A prime number is a number that is divisible by only two numbers – themselves and 1
Confused about your next job?
Input: n =10
Output: 2 3 5 7
Explanation: Only 4 prime numbers are there which are less than or equal to 10.

Input: n = 20 
Output: 2 3 5 7 11 13 17 19
Explanation: All above numbers are prime which are less than or equal to 20.
Simple Approach
Iterate from 2 to N, and check for prime. If it is a prime number, print the number. Below is the implementation of the above approach
C++ Implementation
int checkPrime(int n) < if (n // Function to print all the prime numbers from // range 2 to n void printPrime(int n) < for (int i = 2; i >
 
Java Implementation
 
class Interviewbit < static int isPrime(int n) < for (int i = 2; i < n; i++) if (n % i == 0) return 0; return 1; >static void printPrime(int n) < for (int i = 2; i > >
 
Python Implementation
 
def isPrime(n): # Corner case if n 
Time complexity: O(N*N), Where N is the number.
Space complexity: O(1)
Efficient Approach: Sieve of Eratosthenes
The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so. Following is the algorithm to find all the prime numbers less than or equal to a given integer n by the Eratosthenes method:
When the algorithm terminates, all the numbers in the list that are not marked are prime.

  
Firstly write all the numbers from 2,3,4…. n
  
Now take the first prime number and mark all its multiples as visited.
  
Now when you move forward take another number which is unvisited yet and then follow the same step-2 with that number.
  
All numbers in the list left unmarked when the algorithm ends are referred to as prime numbers.

Dry run of the above approach
Step 1: The numbers between 1 and 100 are listed in the table below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

Step 2: The next step is to write in bold all the multiples of 2, except 2 itself.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

Step 3: Now bold all multiples of 3, 5, and 7 and only leave these numbers.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

Step 4: Since the multiples of 11, 13, 17, and 19 are not present on the list, 1 is finally shaded because it is not prime.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

Step 5: The unshaded numbers are prime. They include:
2, 3, 5,7, 11, 13,17,19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97.
C++ Implementation Efficient Approach
void SieveOfEratosthenes(int n) < bool prime[n + 1]; memset(prime, true, sizeof(prime)); for (int p = 2; p * p > for (int p = 2; p
Java Implementation of Efficient Approach
class SieveOfEratosthenes < void sieveOfEratosthenes(int n) < boolean prime[] = new boolean[n + 1]; for (int i = 0; i > for (int i = 2; i > >
 
Python Implementation of Efficient Approach
 
def SieveOfEratosthenes(n): prime = [True for i in range(n+1)] p = 2 while (p * p 

Time complexity of Sieve of Eratosthenes:
Space complexity: O(1)
Analysis of Time Complexity

PREREQUISITE: Time complexity of the Harmonic Series is O(logN), when N is tending to infinity.
If we analyze our sieve for larger numbers then we can see .

The inner loop at each iteration can be expressed by:
i=2, the inner loop will be executed → upper bound is (n/2) times
i=3, the inner loop will be executed → upper bound is (n/3) times
i=5, the inner loop will be executed → upper bound is (n/5) times
…
i=n(if prime number), the inner loop will be executed → upper bound is 1 times.


n/2 + n/4 + ..+ 1 → n (1/2 + 1/3 + 1/4 + … 1/n),


n (1/2 + 1/3 + 1/5 + 1/7 + 1/ 11 + 1/13 + …).= logn That is why, in some article,

Conclusion
The outer loop is a general for-loop from 1 to N, the time complexity is O(N). The total time complexity is O(NloglogN).
Practice Questions
Frequently Asked Questions
Q: How fast is Sieve of Eratosthenes?
A: It is very fast as it can store prime numbers up to the 1e7 range easily.
Q: How do you improve the sieve of Eratosthenes?
A: We can further improve the sieve to O(n) by writing it to an iterative sieve.
Q: How does the Sieve of Eratosthenes work?
A: It works on the principle of cancellation of prime factors.
Источник