Counting Prime Numbers: Sieve of Eratosthenes using Java

Hobby Codes

Hello readers. Hope you all had a good week.

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. Here are some example execution times.

CountPrime 5000 = 669 (Result in 10 seconds)
CountPrime 10000 = 1229 (Result in 85 seconds)

As you may infer from the trend, if we want to use this method to calculate number of primes till a million or a billion it would be, well a couple of days if not weeks of computer processing.

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.

View original post 685 more words

Counting Prime Numbers: Sieve of Eratosthenes using Java

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s