A prime number is a natural (whole) number that is greater than or equal to two, that can only be divided by itself and 1. The first prime numbers are: 2, 3, 5, 7, etc.
For the number 5, the number of prime numbers that are up to and/or including 5 are:
2, 3, 5
For the number 8, the number of prime numbers that are up to and/or including 8 are:
2, 3, 5, 7
For the number 19, the number of prime numbers that are up to and/or including 19 are:
2, 3, 5, 7, 11, 13, 17, 19
For the number 25, the number of prime numbers that are up to and/or including 25 are:
2, 3, 5, 7, 11, 13, 17, 19, 23
For the number 36, the number of prime numbers that are up to and/or including 36 are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31
For the number 37, the number of prime numbers that are up to and/or including 37 are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
These lists are just examples. There are many other example lists of prime numbers below and/or including a given number. Begin the understanding of the Sieve of Eratosthenes by noting that the prime numbers below a smaller given number are the same as the first part of the prime numbers below a given bigger number.
The Sieve of Eratosthenes is a technique to find all the prime numbers that are less than or equal to a given number such as 36 or 37 above. This number such as 36 or 37 is usually given the variable name “n” in programming. The Sieve of Eratosthenes is considered as an efficient algorithm to obtain the list of prime numbers.
Demonstration for Sieve of Eratosthenes
The question is: find the prime numbers less than or equal to 5, for example, in an efficient way. The efficient way here means using as few operations as possible. The prime numbers begin from 2. All the numbers including the multiples of small prime numbers from 2 to 5 are:
2, 3, 4, 5
In this range, a number that is not a prime number is a multiple of a previous prime number. A multiple can be obtained by addition of the same prime number, over and over. For example, 2 + 2 is 4, plus 2 again is 6. And that goes on beyond the range. Four, which is a multiple of 2, should not be on the list because it is not a prime number. The equation 3 + 3 is 6, which is already beyond the range. And 6 or any number beyond the range should not be on the list. So, the result is as follows:
2, 3, 5
The number in question here is 5. The square root of 5 is 2.24. The integer value for the square root of 5 is 2. The multiples of prime numbers below and up to 2, which is the integer value for the square root of 5, are removed from the list of all the numbers.
Consider now, the number 8. All the numbers including the multiples of small prime numbers from 2 to 8 are:
2, 3, 4, 5, 6, 7, 8
The equation 2 + 2 is 4. Four goes out. The equation 4+2 is 6. Six goes out. The equation 6 + 2 is 8. Eight is out. The next prime number to consider is 3. The equation 3 + 3 is 6. Six is already ruled out by the continuous addition of 2. The equation 6 + 3 is 9; that is out of range. The prime numbers between 2 and 8, inclusive, are:
2, 3, 5, 7
The number in question here is 8. The square root of 8 is 2.83. The integer value for the square root of 8 is 2. The multiples of the prime numbers below and up to 2 which is the integer value for the square root of 8 are removed to obtain the required list of prime numbers.
A similar problem is to list the prime numbers from 2 to 19, inclusively. All the numbers from 2 to 19, inclusive are:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
The equation 2 + 2 is 4; 4 is out. The equation 4 + 2 is 6; 6 is out. The equation 6 + 2 is 8; 8 is out. The equation 8 + 2 is 10; 10 is out. The equation 10 + 2 is 12; 12 is out. The equation 12 + 2 is 14; 14 is out. The equation 14 + 2 is 16; 16 is out. The equation 16 + 2 is 18; 18 is out. The equation 18 + 2 is 20, which is above the range; 20 is out.
The next prime number to consider, going upwards towards the square root of 19, is 3. The equation 3 + 3 is 6; 6 is already ruled out as a multiple of 2. The equation 6 + 3 is 9; 9 goes out. The equation 9 + 3 is 12; 12 is already ruled out as a multiple of 2. The equation 12 + 3 is 15; 15 is out. The equation 15 + 3 is 18; 18 is already ruled out as a multiple of 2. The equation 18 + 3 is 21, which is above the range. The result is:
2, 3, 5, 7, 11, 13, 17, 19
The number in question here is 19. The square root of 19 is 4.36. The integer value for the square root of 19 is 4. The multiples of prime numbers below and up to 4 which is the integer value for the square root of 19 are removed.
The prime numbers below and up to 4 are: 2 and 3. Due to 3, there was no point in removing the numbers 6, 12, and 18 that are multiples of 3, which is already removed as multiples of 2. Only the multiples of 3 that are not multiples of 2 are removed because of 3. In practice, after removing the multiples of 2, only the multiples from and above 3 x 3 = 9 should be removed without repeating the removal of 6. Because of 3, the numbers to be removed are 9, 12, 15, and 18; with 12 and 18 removed two times in theory. Number 6 should be removed once and not twice.
Let n be 25, a new number in question. All the numbers from 2 to 25 are:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
The equation 2 + 2 is 4; 4 goes out. The equation 4 + 2 is 6; 6 is out. The equation 6 + 2 is 8; 8 is out. The equation 8 + 2 is 10; 10 is out. The equation 10 + 2 is 12; 12 is out. The equation 12 + 2 is 14; 14 is out. The equation 14 + 2 is 16; 16 is out. The equation 16 + 2 is 18; 18 is out. The equation 18 + 2 is 20; 20 is out. The equation 20 + 2 is 22; 22 is out. The equation 22 + 2 is 24; 24 is out. The equation 24 + 2 is 26, which is above the range.
The next prime number to consider, going upwards towards the square root of 25, is 3. The equation 3 + 3 is 6; 6 is already ruled out as a multiple of 2. The equation 6 + 3 is 9; 9 goes out. The equation 9 + 3 is 12. Twelve is already ruled out as a multiple of 2. The equation 12 + 3 is 15; 15 is out. The equation 15 + 3 is 18; 18 is already ruled out as a multiple of 2. The equation 18 + 3 is 21; 21 goes out. The equation 21 + 3 is 24; 24 is already ruled out as a multiple of 2. The equation 24 + 3 is 27, which is above the range.
The next prime number to consider, going upwards towards the square root of 25 which is 5, is 5. The equation 5 + 5 is 10; 10 is already ruled out as a multiple of 2. The equation 10 + 5 is 15; 15 is already ruled out as a multiple of 3. The equation 15 + 5 is 20; 20 is already ruled out as a multiple of 2. The equation 20 + 5 is 25; 25 goes out. The result is:
2, 3, 5, 7, 11, 13, 17, 19, 23
The number in question here is 25. The square root of 25 is 5. The integer value for the square root of 25 is 5. The multiples of prime numbers below and up to 5, which is the integer value for the square root of 25, are removed.
The prime numbers below and up to 5 are 2, 3, and 5. Due to 2, the numbers that are supposed to be removed from the list of all the numbers by multiples are: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 and 24. Due to 3, the numbers that are supposed to be removed from the list by multiples are: 6, 9, 12, 15, 18, 21 and 24. Due to 5, the numbers that are supposed to be removed by multiples are: 10, 15, 20 and 25.
By all multiples, the removals are as follows:
2 : 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24
3 : 6, 9, 12, 15, 18, 21, 24
5 : 10, 15, 20, 25
By multiples, 6 is removed two times (in theory), 10 is removed two times (in theory), 12 is removed two times (in theory), 15 is removed two times (in theory), 20 is removed two times (in theory), and 24 is removed two times (in theory).
However, if due to 3, the removal begins from 3 x 3 = 9, then 6 is removed only once. If due to 5, the removal begins from 5 x 5 = 25, then the removal of 10, 15, and 20 is done once each. However, the removal of 12, 18, and 24 is still done two times per number. Still, there would be some advantage, as four repeated operations of removal are omitted (for 6, 10, 15 and 20). This improves the efficiency (time complexity). With that, the removals will be:
2 : 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24
3 : 9, 12, 15, 18, 21, 24
5 : 25
The numbers 6, 10, 15, and 20 have each been removed once, instead of two times. The numbers, 12, 18 and 24 have each been removed two times. As of now, nothing can be done to remove 12, 18, and 24 only once.
The situations for the numbers 36 and 37, or any other number greater than 1, are similarly explained.
Avoiding Redundancy
By just removing the multiples of prime numbers from 2 to the integer value of √n, the required set of prime numbers is obtained. The efficiency can be improved by removing the multiples of prime numbers, beginning from the square of the prime number (i2) up to the integer value of √n as previously suggested. This omits some number removal operations. So, reducing the total number of operations. The Sieve of Eratosthenes is done by this second approach.
Algorithm of Sieve of Eratosthenes
The algorithm begins by making a zero based indexed vector of length which is n+1. Each element of this vector is initialized to Boolean, true, except the first and second elements for index 0 and index 1 that are initialized to false. For this vector, the index 2 corresponds to the number (prime) 2; the index 3 corresponds to the number (prime) 3; the index 4 corresponds to the number 4; and so on. Since the vector is zero a based index, the length has to be n+1 so that the last index corresponds to n.
An index number for this vector list which has to be removed is not removed per se: the value of the index number is made false to indicate the removal. That is, the element is given the false value. So, if a number (index) has to be removed from the list (vector) more than once, the value for the index is made false more than once.
At the end, the indexes for the elements of the vector whose values remained true are read out as the prime numbers.
Before then, the multiples of prime indexes beginning from the square of the prime index (i2) up to the integer value of √n are marked as false.
C++ Coding
The program in C++, should begin with the following:
#include <vector>
using namespace std;
The Sieve of Eratosthenes function is as follows:
vector<bool> sieve(n+1, true);
sieve[0] = false;
sieve[1] = false;
int i = 2;
while (i * i <= n) {
if (sieve[i] == true) { // if i is prime number
int j = i * i;
while (j <= n) { //marking multiples with false
sieve[j] = false;
j = j + i; //increment by multiple
}
}
i = i + 1; // normal increment of outer loop, by 1
}
return sieve;
}
Read the comments of the code. The name of the function is sieve(). The returned vector, after all the multiples are marked as false, is also called sieve. A suitable C++ main function for this code is:
{
vector<bool> vtr = sieve(37);
for (int i=0; i<vtr.size(); i++)
if (vtr[i] == true)
cout << i << ' ';
cout << endl;
return 0;
}
With this code, the output is as follows:
2 3 5 7 11 13 17 19 23 29 31 37
The time complexity for this function is O(n log log n).
Conclusion
The algorithm begins by making a zero based indexed vector of the length n+1. Each element of this vector is initialized to Boolean, true, except the first and second elements for index 0 and index 1 that are initialized to false. For this vector, each index is a number of interest. Since the vector is zero based indexed, the length has to be n+1 so that the last index is n.
The value of the number which is the index is made false to indicate the removal. That is, the element is given the false value.
At the end, the indexes for the elements of the vector whose values remained true are read out as the prime numbers.
Before then, the multiples of prime indexes beginning from the square of the prime index up to the integer value of √n are marked as false.
