Sieve of Eratosthenes Algorithm in C++
This article will explain how to implement the sieve of eratosthenes algorithm in C++.
Implement Sieve of Eratosthenes Algorithm Using std::vector Container in C++
Sieve of Eratosthenes is one of the prime number sieves, representing relatively efficient algorithms for finding primes. There are multiple algorithms suited for different prime number ranges, and they also have contrasting performance characteristics.
Sieve of Eratosthenes can be considered the easiest one to implement, and it is quite efficient on smaller ranges. Even though its running time complexity is O(N loglogN), it performs better on smaller ranges.
This article will implement this algorithm using the most straightforward method to be suited for the introductory article. The algorithm takes the integer value and finds all prime numbers less than or equal to the given integer.
At first, we construct an array of boolean values which has the same size as the given integer and initialize every element to have a true value.
Then we iterate through this array of elements and store false value if the given element has a composite index. We access the array indices by calculating the multiples of consecutive primes starting from the smallest one - 2 and we stop the iteration once the square of the given prime is larger than the input integer - n. The previous steps are implemented using the nested for loops in the printPrimesLessThanN function.
Finally, we cycle through this vector and print the element indices that have true value stored. Note that the latter operation is handled by the for loop at the end of the printPrimesLessThanN function. We also provide driver code in the main function to accept the integer denoting the upper bound from the user and validate the input until it is passed to the printPrimesLessThanN function.
#include <cstring>
#include <iostream>
#include <limits>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
void printPrimesLessThanN(unsigned long long n) {
vector<bool> table(n, true);
for (unsigned long long p = 2; p * p < n; p++) {
if (table[p] == true) {
for (unsigned long long i = p * p; i < n; i += p) table[i] = false;
}
}
for (unsigned long long p = 2; p < n; p++)
if (table[p]) cout << p << " ";
}
int main() {
unsigned long long integer;
while (true) {
cout << "Enter integer: ";
if (cin >> integer) {
break;
} else {
cout << "Enter a valid integer value!\n";
cin.clear();
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
}
cout << "Following prime numbers are smaller than given integer: \n";
printPrimesLessThanN(integer);
return EXIT_SUCCESS;
}
Output:
Enter integer: 30
Following prime numbers are smaller than given integer:
2 3 5 7 11 13 17 19 23 29
The previous code snippet is a working example that can be optimized with various methods like exploiting concurrency in the program, slicing and storing the array in memory so that the data access is optimized, or using other algorithmic insights. Although, there is one tiny insight that can save multiples of running time for this implementation without making huge changes, and that is to store true/false values in the vector of chars.
As you can observe by running multiple tests on larger numbers, the bool type performs quite worse than the integral type like char or even int. The following code sample shows the simple benchmark scenario for both versions of the function - printPrimesLessThanN and prints the elapsed time at the end of the program.
#include <sys/time.h>
#include <cstring>
#include <iostream>
#include <limits>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
float time_diff(struct timeval *start, struct timeval *end) {
return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}
void printPrimesLessThanN(unsigned long long n) {
vector<bool> table(n, true);
struct timeval start {};
struct timeval end {};
gettimeofday(&start, nullptr);
for (unsigned long long p = 2; p * p < n; p++) {
if (table[p] == true) {
for (unsigned long long i = p * p; i < n; i += p) table[i] = false;
}
}
gettimeofday(&end, nullptr);
printf("printPrimesLessThanN1: %0.8f sec\n", time_diff(&start, &end));
}
void printPrimesLessThanN2(unsigned long long n) {
vector<char> table(n, 1);
struct timeval start {};
struct timeval end {};
gettimeofday(&start, nullptr);
for (unsigned long long p = 2; p * p < n; p++) {
if (table[p] == 1) {
for (unsigned long long i = p * p; i < n; i += p) table[i] = 0;
}
}
gettimeofday(&end, nullptr);
printf("printPrimesLessThanN2: %0.8f sec\n", time_diff(&start, &end));
}
int main() {
unsigned long long integer;
while (true) {
cout << "Enter integer: ";
if (cin >> integer) {
break;
} else {
cout << "Enter a valid integer value!\n";
cin.clear();
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
}
printPrimesLessThanN(integer);
printPrimesLessThanN2(integer);
return EXIT_SUCCESS;
}
Output:
Enter integer: 1000000000
printPrimesLessThanN1: 47.39665985 sec
printPrimesLessThanN2: 10.11181545 sec
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook