Skip to content
June 22, 2011 / oop123

My Eratosthenes Sieve

I may as well post the class I used to generate the primes I use for Project Euler questions.

Source Code on GitHub

It’s a pretty simple implementation (the BitEratosthenesSieve is just EratosthenesSieve using a BitSet instead of a boolean array). I also used an interface in case someday in the distant future when I can actually write an Atkin’s Sieve. While writing EratosthenesSieve, I experienced one of the OOP’s principles – encapsulation and information hiding – first hand.

The first implementation I used for EratostheneSieve includes even numbers, which is a huge waste of memory given we already know they are not primes (excluding 2). As a result, I wrote a new implementation remove testing even numbers in the Sieve, so the class only sieve for primes in odd numbers. It uses 50% less memory than the first implementation and has a (theoretical) ~20% increase in speed. Now, if I had simply written a method that gives me a “raw” boolean array and change the implementation, I would have to change existing code and write extra code in order to use the sieve. By wrapping the sieve in a class, I can change the implementation without breaking any code.

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: