Re: Shootout: the benchmarks game.

  I'm curious to know how fast this program would be when translated to
Java. In my computer (3.4GHz Pentium4) using gcc 4.1.2 (with the options
-O3 -march=pentium4 -fomit-frame-pointer) it takes 1 min and 17 seconds,
while taking 252 MB of memory (according to 'top').

  The task the program solves is in the comment. (Note that I'm not
really asking how fast the *problem* can be solved in Java, but how fast
it can be solved by using this same algorithm/technique.)

/*
  Find the largest n for which:

1) n is a prime.
2) The nth prime is smaller than 4200000000.

  As the answer, print both n and the nth prime.
And while you are at it, also print the amount of
primes smaller than 4200000000.
 */

#include <bitset>
#include <iostream>

namespace
{
    const unsigned MAX_VALUE = 4200000000U;
    std::bitset<MAX_VALUE/2> prime;

    // http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    void init()
    {
        prime.set();
        for(unsigned n = 3; n*n < MAX_VALUE; n += 2)
            if(prime.test(n/2))
                for(unsigned index = n*n; index < MAX_VALUE; index += n)
                    if(index % 2)
                        prime.reset(index/2);
    }
}

#include <ctime>

int main()
{
    const clock_t t1 = std::clock();
    init();

    unsigned count = prime.count(), p = MAX_VALUE+1;

    std::cout << "There are " << count << " primes smaller than "
              << MAX_VALUE << std::endl;

    while(true)
    {
        do p -= 2; while(!prime.test(p/2));
        if(count%2 && prime.test(count/2)) break;
        --count;
    }

    const int seconds = (std::clock() - t1)/CLOCKS_PER_SEC;
    std::cout << count << "\n" << p << std::endl
              << seconds/60 << " mins " << seconds%60 << " s\n";
}