Friday, April 15, 2011

More explorations of primes

So I decided to add a little more to detail to the statistics generation for my c++ implementation of the Sieve of Eratosthenes. I added code to tally the occurrences of twin primes, prime triplets, and prime quadruplets.

Twin primes are defined as the set p, p+2 . Prime triplets are defined as either the set p, p+2, p+6 or p, p+4, p+6. Prime quadruplets are defined as the set p, p+2, p+6, p+8.

I also modified the implementation to use the bit being cleared as being a prime and a bit being set a composite. This allowed me to remove the O(n) code that initialized the bit array to a set state.

Here are the results of a run for 1 billion:

snits@jsni-linux:~/proj/cxx=>time ./tps2 1000000000
50847534 primes between 2 and 1000000000, 3424506 twin primes,
759256 prime triplets, and 28388 prime quadruplets.
The greatest prime is 999999937

real    2m27.192s
user    2m27.041s
sys     0m0.117s

No comments:

Post a Comment