Java Collections Framework - Building Java Programs: A Back to Basics Approach - page 688

numbers: (5, 7, 11, 13, 17, 19, 23, 25)
primes: (2, 3)
numbers: (7, 11, 13, 17, 19, 23)
primes: (2, 3, 5)
Now let's implement the sieve algorithm. We'll use LinkedList s to represent the
lists of numbers and primes. This tool is preferable to ArrayList s because, as we dis-
cussed previously, removing elements from the front of an ArrayList is inefficient.
First we'll create an empty list of primes and a list of all the numbers up to the
given maximum. Since we've discussed ADTs and the List interface, we'll declare
our variables as the ADT interface type List<Integer> :
List<Integer> primes = new LinkedList<Integer>();
List<Integer> numbers = new LinkedList<Integer>();
for (int i = 2; i <= max; i++) {
numbers.add(i);
}
Next, we'll process the list of numbers. We'll use an iterator to make passes over
the numbers list and remove elements that are multiples of the front element:
while (!numbers.isEmpty()) {
// remove a prime number from the front of the list
int front = numbers.remove(0);
primes.add(front);
// remove all multiples of this prime number
Iterator<Integer> itr = numbers.iterator();
while (itr.hasNext()) {
int current = itr.next();
if (current % front == 0) {
itr.remove();
}
}
}
The lines of code that follow are the complete program. The most significant addi-
tion is a main method that prompts the user for the maximum number:
1 // Uses a linked list to implement the sieve of
2 // Eratosthenes algorithm for finding prime numbers.
3
4 import java.util.*;
5
6 public class Sieve {