programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Sieve of Eratosthenes using a set

Carmine Gendry
Greenhorn
Posts: 17
Hello, I'm given the following problem:

Print prime #'s between 2 - n using this algorithm:
- Insert ALL #'s between 2 - n into set.
- Remove multiples of 2 from set, except 2.
- Remove multiples of 3 from set, except 3.
- Continue process till square root of n.
- Print the set.

I've been stuck for the last couple of hours after simply getting all the #'s between 2 - n into the set and was hoping you guys can help me out in understanding this.
This is what I currently have, which isn't much:

I appreciate any help in the right direction!

Knute Snortum
Sheriff
Posts: 4274
127
You've started well.  Now, how to remove multiples of two.  Have you tried just doing multiples of two and not worrying about the other multiples?  This sometime helps to get your brain going in the right direction.

Junilu Lacar
Sheriff
Posts: 11477
180
So what are you stuck on? You have done the "Insert ALL #'s between 2 - n into set" part, what's keeping you from trying to do the "Remove multiples of 2 from set, except 2" part?

Carmine Gendry
Greenhorn
Posts: 17
Knute Snortum wrote:You've started well.  Now, how to remove multiples of two.  Have you tried just doing multiples of two and not worrying about the other multiples?  This sometime helps to get your brain going in the right direction.

Junilu Lacar wrote:So what are you stuck on? You have done the "Insert ALL #'s between 2 - n into set" part, what's keeping you from trying to do the "Remove multiples of 2 from set, except 2" part?

The problem that I run in to is how to remove the multiples of two while using the iterator to iterate through the set.

Carmine Gendry
Greenhorn
Posts: 17
It's amazing what a simple post, and a few replies on these forums can do.
So this is where I'm currently at:

Junilu Lacar
Sheriff
Posts: 11477
180
That's a good step forward. I must warn you in advance that your instructions are flawed.  The part that says "Continue process till square root of n" is misleading and open to interpretation. To prove my point, tell us what you think that instruction means. I'd bet a beer it's going to be misguided.

Junilu Lacar
Sheriff
Posts: 11477
180
A couple of things to nitpick about your last code listing posted:

1. You really should align your braces properly. Misaligned braces make your code difficult to read and misleading. Code that's hard to read can lead to bugs. Code that's misleading attracts bugs. The closing brace on line 17 should be aligned with the closing brace on line 12. The closing brace on line 19 should have the same indentation level as the public keyword on line 8 and line 21.