programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Queues and the Sieve of Eratosthenes

Greenhorn
Posts: 23
• Number of slices to send:
Optional 'thank-you' note:
Greetings, Java programmers! I am seeking your wisdom once again for an error I can't seem to quite put my finger on. I am working on a problem that computes primes. Here is the problem:

You are going to implement a class that computes all the primes up to some integer n. The technique you are to use was developed by a Greek named Eratosthenes who lived in the third century BC. The technique is known as the Sieve of Eratosthenes. The algorithm is described by the following pseudocode:

create a queue and fill it with the consecutive integers 2 through n inclusive.
create an empty queue to store primes.
do {
obtain the next prime p by removing the first value in the queue of numbers.
put p into the queue of primes.
go through the queue of numbers, eliminating numbers divisible by p.
} while (p < sqrt(n))
all remaining values in numbers queue are prime, so transfer them to primes queue

You are to use the Queue interface provided. When you want to construct a Queue object, you should make it of type LinkedQueue. These classes are included.
You should define a class called Sieve with the following public methods:

Sieve() - Constructs a sieve object.

void computeTo(int n) - This is the method that should implement the sieve algorithm. All prime computations must be implemented using this algorithm. The method should compute all primes up to and including n. It should throw an IllegalArgumentException if n is less than 2.

void reportResults() - This method should report the primes to System.out. It should throw an IllegalStateException if no legal call has been made yet on the computeTo method. It is okay for it to have an extra space at the end of each line.

int getMax() - This is a convenience method that will let the client find out the value of n that was used the last time computeTo was called. It should throw an IllegalStateException if no legal call has been made yet on the computeTo method.

int getCount() - This method should return the number of primes that were found on the last call on computeTo. It should throw an IllegalStateException if no legal call has been made yet on the computeTo method.

Your reportResults method should print the maximum n used and should then show a list of the primes, 12 per line with a space after each prime. Notice that there is no guarantee that the number of primes will be a multiple of 12. The calls on reportResults must exactly reproduce the format of the sample log. The final line of output that appears in the log reporting the percentage of primes is generated by the main program, not by the call on reportResults.

Here is my class Sieve. I am having difficulty getting all the primes into the proper queue:

When I input say, 20, I only get 2, 3, and 11 back as primes. Somewhere in the algorithm (lines 40-54) I seem to have gone awry, but I'm not certain where. If anyone can see how or why, I'd greatly appreciate the correction!

Here are the other classes:

SieveMain:

Queue:

Thank you very, very much!

lowercase baba
Posts: 13091
67
• Number of slices to send:
Optional 'thank-you' note:

fred rosenberger
lowercase baba
Posts: 13091
67
• Number of slices to send:
Optional 'thank-you' note:
so going through your logic...you build a list of ints from 2 to 20.

lines 43 - 54 are the meat of your algorithm. the first time through, you move 2 to the primes queue, and effectively eliminate the even numbers.

You then move 3 to the primes queue, and eliminate those multiples. your num list now holds:

5,7,11,13,17,19

I would think you would them move in 5, and eliminate 15 as a candidate. But then, your loop quit because num (which is now 5) is NOT < sqrt of 20.

What I would suggest you do is write a method that prints everything in a queue. Then call it after each iteration to make sure it is eliminating the correct numbers, and that what is left has not be re-arranged.

Laura Peterson
Greenhorn
Posts: 23
• Number of slices to send:
Optional 'thank-you' note:
Oops! Sorry about that! I've edited the original post to contain the correct LinkedQueue class. Thanks for the advice about the queue. Are you saying that I should actually create an iterator? Thank you!

Laura Peterson
Greenhorn
Posts: 23
• Number of slices to send:
Optional 'thank-you' note:
I've changed the computeTo method to this:

Any reason why I am getting the number 3 twice?

fred rosenberger
lowercase baba
Posts: 13091
67
• Number of slices to send:
Optional 'thank-you' note:

Laura Peterson wrote:Any reason why I am getting the number 3 twice?

The obvious answer to that is "yes". WHY you are getting the number 3 twice is a much harder question.

Seriously, I am a big fan of putting in System.out.println() statements to see what your code is REALLY doing. They can always be take out later, but but them in. Use a smaller input if that makes it easier - say of 10 instead of 20.