Hi,
I wrote this implementation of Sieve of Eratosthenes, is there any way I could eek some more performance out of it. As in opitmising data types, calculations etc.
#include <iostream> // cout
#include <math.h> // sqrt
#include <time.h> // clock/CLOCKS_PER_SEC
#include <stdlib.h> // malloc/free
using namespace std;
int main(int argc, const char * argv[]) {
size_t n = 1000000000;
int i;
int j;
int k;
int s;
int c;
int sr;
int * a = (int*)malloc(n * sizeof(int));
clock_t t = clock();
for(i = 0; i < n; i++) {
a[i] = 1;
}
sr = sqrt(n);
for(i = 2; i <= sr; i++) {
if(a[i]) {
s = i * i;
for(k = 0, j = 0; j <= n; j = s + (k * i), k++) {
a[j] = 0;
}
}
}
t = clock() - t;
c = 0;
for(i = 2; i < n; i++) {
if(a[i]) {
c++;
}
}
cout << fixed << "Calculated " << c << " prime numbers up to " << n << " in " << t << " clocks (" << ((float)t) / CLOCKS_PER_SEC << " seconds).\n";
free(a);
return 0;
}
Currently, I get the following performance:
"Calculated 78498 prime numbers up to 1000000 in 7634 clocks (0.007634 seconds)."
"Calculated 664579 prime numbers up to 10000000 in 130416 clocks (0.130416 seconds)."
"Calculated 50847534 prime numbers up to 1000000000 in 19063075 clocks (19.063076 seconds)."
Thanks in advance.
