Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Compare the runtime of the sieve against vectors and bool arrays
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
bool* boolPrimeSieveMemset(int64_t size) {
bool* prime = new bool[size + 1];
memset(prime, true, size + 1); //faster than loops and vectors
prime[0] = false;
prime[1] = false;
for (int64_t p = 2; p*p <= size; p++) {
if (prime[p] == true) {
for (int64_t i = p * 2; i <= size; i += p) {
prime[i] = false;
}
}
}
return prime;
}
bool* boolPrimeSieveLoops(int64_t size) {
bool* prime = new bool[size + 1];
for(int i = 0; i <= size; ++i){
prime[i] = true;
}
prime[0] = false;
prime[1] = false;
for (int64_t p = 2; p*p <= size; p++) {
if (prime[p] == true) {
for (int64_t i = p * 2; i <= size; i += p) {
prime[i] = false;
}
}
}
return prime;
}
vector<bool> vectorPrimeSieve(int64_t size){
vector<bool> prime(size+1);
for(int i = 0; i <= size; ++i){
prime[i] = true;
}
prime[0] = false;
prime[1] = false;
for (int64_t p = 2; p*p <= size; p++) {
if (prime[p] == true) {
for (int64_t i = p * 2; i <= size; i += p) {
prime[i] = false;
}
}
}
return prime;
}
int main(){
int size;
cout << "Enter the size: ";
cin >> size;
clock_t start = clock();
bool* a = boolPrimeSieveMemset(size);
clock_t end = clock();
double time = (double)(end - start) / CLOCKS_PER_SEC * 1000.0;
cout << "Memset: " << time << " ms" << endl;
delete[] a;
start = clock();
bool* b = boolPrimeSieveLoops(size);
end = clock();
time = (double)(end - start) / CLOCKS_PER_SEC * 1000.0;
cout << "Loops: " << time << " ms" << endl;
delete[] b;
start = clock();
vector<bool> c = vectorPrimeSieve(size);
end = clock();
time = (double)(end - start) / CLOCKS_PER_SEC * 1000.0;
cout << "Vector: " << time << " ms" << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment