Re: [Algorithm] Sum of Primes < 1000000

So to make a long story short, the algorithm is:

* Make array of booleans of length max_num - 1, whose zeroth element
corresponds to 2 and whose max_num - 2nd element corresponds to maxnum.
Clear it (all false). (Java clears it for you if you use Java.)
* Take square root of maxnum and store it somewhere.
* for i = 2 to that square root
* if (array[i - 2]) continue;
* for j = i*i to max_num step i
* set array[j - 2]
* end
* end

Note the optimization of starting the inner loop at i*i. All the
composites smaller than i*i have a prime factor smaller than i and so
are already marked at that point. Note also skipping the inner loop for
composite values of i.

In fact, using the square root of max_num is a less significant
optimization after the i*i optimization, as it just stops the outer loop
testing every remaining value for compositeness and then entering the
inner loop for the primes but without the inner loop actually doing
anything (as i*i >= max_num the loop terminates immediately).

The algorithm does sqrt(max_num) bit tests (using the sqrt(max_num) opt)
and sum{primes p up to sqrt(max_num}(max_num/p). The number of primes is
O(log sqrt(max_num)) from what I've seen of primes, which is O(log
max_num) since the log of the square root is simply half the log and the
half disappears into the constant factor. The average prime from this
set will be O(1) (integral of log x is log x - x, approximates sum of
primes; divide by log x for 1 - 1/log(x) is O(1)). So the number of bit
sets is O(max_num log max_num) -- O(max_num) per prime as it's max_num/p
with average p O(1), and O(log max_num) primes.

So the whole thing has complexity O(n log n) -- as good as quicksort,
and without the quadratic worst-case behavior. :)

Removing the squaring/square rooting optimizations doesn't increase the
complexity but does increase the running time by a factor of 2 or so.
Note that square roots are expensive, but the only square root occurs
outside any loops...i*i is just a multiplication, and multiplication of
integers is cheap on any modern architecture. The inner loop does one
imul, three iadds (one's actually the subtract in the loop test and one
computes the array index), one icmp (the rest of the loop test), and one
boolean assignment. I expect the compiler to optimize "set array[j - 2]"
to "*(foo + j) = true" or something equivalent -- i.e. to use a point
two before the actual start of the array as the base for the pointer
adds in this loop. Of course, using a BitSet instead of a boolean[] may
change this a lot. A sensible implementation plus jit compiler will
probably reduce it to a similar add and a bit mask operation, but I
expect an idiv will sneak in there to get the array index into the
underlying array, which may make BitSet worse-performing, and the
subtraction of 2 definitely has to be done separately. Likely *(foo + (j
- 2)/64) |= 2^(j - 2) under the hood with 2^(j - 2) sucked out of a
lookup table, for a grand total of two extra iadds (j - 2 and the lookup
into the 2^n table), one extra idiv, and two extra fetches (the lookup
into the 2^n table and retrieving the stored word to |= with something)
versus storing in a boolean[] which is probably the one add and a flat
store, without bothering to retrieve whatever was in the array cell
originally.

I'd be *very* surprised if BitSet actually comes out faster after you
run it a few hundred times to get it all JITted and then a few hundred
more to measure and average.