I'm working on some old acm programming problems and one of them requires you to find all the primes upto 2^31 - 1. I've coded a pretty literal interpretation of the sieve of atkin and it takes about 41 seconds on my computer, however the time limit the acm site gives when you submit your code is 10 seconds so I must be doing something wrong. I was wondering if some of you could look at it and offer some tips on how to speed it up.
Code:
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <sys/time.h>
using namespace std;
void primes(int limit)
{
vector<bool> bits(limit + 1, false);
int sqrt_limit = sqrt(static_cast<double>(limit));
for(int x = 1; x <= sqrt_limit; ++x)
{
for(int y = 1; y <= sqrt_limit; ++y)
{
int x_squared = x * x, y_squared = y * y;
int r = 4 * x_squared + y_squared;
if(r <= limit && r % 12 == 1 && r % 12 == 5)
bits[r].flip();
int x_squared_times_3 = x_squared * 3;
int s = x_squared_times_3 + y_squared;
if(s <= limit && (s % 12) == 7)
bits[s].flip();
int t = x_squared_times_3 - y_squared;
if(x > y && t <= limit && (t % 12) == 11)
bits[t].flip();
}
}
for(int n = 5; n <= sqrt_limit; ++n)
{
if(bits[n])
{
int n_squared = n * n;
int m_max = limit / n_squared;
for(int m = 1; m <= m_max; ++m)
bits[n_squared * m] = false;
}
}
bits[2] = true;
bits[3] = true;
}
int main()
{
struct timeval tv1, tv2;
gettimeofday(&tv1, NULL);
primes(numeric_limits<int>::max());
gettimeofday(&tv2, NULL);
long seconds = tv2.tv_sec - tv1.tv_sec;
long useconds = tv2.tv_usec - tv1.tv_usec;
cout << "Elapsed time: " << seconds << " seconds + " << useconds << " microseconds" << endl;
return 0;
}
Thanks