I've been writing this prime number calculator, and I've gotten it pretty quick in comparison to most I've seen knocking about. This one uses the Sieve of Eratosthenes approach, and I've optimised the code as much as possible with my knowledge. A more experienced mind might be able to make it better.
Machine: 2.4GHz Quad-Core i7 w/ 8GB RAM @ 1600MHz
Compiler: clang++ main.cpp -O3
Benchmarks:
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100 Calculated 25 prime numbers up to 100 in 2 clocks (0.000002 seconds). Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000 Calculated 168 prime numbers up to 1000 in 4 clocks (0.000004 seconds). Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000 Calculated 1229 prime numbers up to 10000 in 18 clocks (0.000018 seconds). Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000 Calculated 9592 prime numbers up to 100000 in 237 clocks (0.000237 seconds). Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000 Calculated 78498 prime numbers up to 1000000 in 3232 clocks (0.003232 seconds). Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000000 Calculated 664579 prime numbers up to 10000000 in 51620 clocks (0.051620 seconds). Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000000 Calculated 5761455 prime numbers up to 100000000 in 918373 clocks (0.918373 seconds). Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000000 Calculated 50847534 prime numbers up to 1000000000 in 10978897 clocks (10.978897 seconds). Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 4000000000 Calculated 189961812 prime numbers up to 4000000000 in 53709395 clocks (53.709396 seconds). Caelans-MacBook-Pro:Primer3 Caelan$
Source:
#include <iostream> // cout
#include <cmath> // sqrt
#include <ctime> // clock/CLOCKS_PER_SEC
#include <cstdlib> // malloc/free
using namespace std;
int main(int argc, const char * argv[]) {
if(argc == 1) {
cout << "Please enter a number." << "\n";
return 1;
}
long n = atol(argv[1]);
long i;
long j;
long k;
long c;
long sr;
bool * a = (bool*)malloc((size_t)n * sizeof(bool));
for(i = 2; i < n; i++) {
a[i] = true;
}
clock_t t = clock();
sr = sqrt(n);
for(i = 2; i <= sr; i++) {
if(a[i]) {
for(k = 0, j = 0; j <= n; j = (i * i) + (k * i), k++) {
a[j] = false;
}
}
}
t = clock() - t;
c = 0;
for(i = 2; i < n; i++) {
if(a[i]) {
//cout << i << " ";
c++;
}
}
cout << fixed << "\nCalculated " << c << " prime numbers up to " << n << " in " << t << " clocks (" << ((float)t) / CLOCKS_PER_SEC << " seconds).\n";
free(a);
return 0;
}