/** For some reason this didn't occur to me for a really long time */
void smartestSieve(int bound, int* primes, int* primeslength) {
primes[0] = 2; primes[1] = 3; primes[2] = 5; int mLength = 3;
int n;
for (n = 7; n < bound; n += 2 * ((2*n) % 3)) {
int isprime = 1;
int i;
for (i = 2; i < mLength; ++i) {
int p = primes[i];
if (p*p > n) {
break;
} else if (n % p == 0) {
isprime = 0;
break;
}
}
if (isprime) {
primes[mLength++] = n;
}
}
*primeslength = mLength;
}
Timing information is below, first, I slotted it into the original graph, removing the two slowest methods:And, to emphasize the "part that matters", its comparison with the recursive method:
The information used to generate these graphs is now on the second page of the sheet linked to in the previous post, https://docs.google.com/spreadsheets/d/18-avzFTZDDOPMh7p_FRPOVc9SVfEhxPEoVFGQPTyNWk/edit?usp=sharing
I am now considering looking at the advantages of hand tooled assembly and/or comparing the same methods in Python.


No comments:
Post a Comment