Counting Prime Numbers: Sieve of Eratosthenes using Java
Hello readers. Hope you all had a good week.
CountPrime 5000 = 669 (Result in 10 seconds)
CountPrime 10000 = 1229 (Result in 85 seconds)
Last week I described here how to count prime numbers in a range using a rather unorthodox method called Hardy-Wright method. But as that method involves calculating factorials of all the numbers in the range [3..n], it is rather slow even when using multi-threading using a 8 core CPU.
So this week I was looking for a fast method to do this thing. I googled a bit and came across a method called Sieve of Eratosthenes.