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

7 public static void main(String[] args) {
8 System.out.println("This program will tell you all prime");
9 System.out.println("numbers up to a given maximum.");
10 System.out.println();
11
12 Scanner console = new Scanner(System.in);
13 System.out.print("Maximum number? ");
14 int max = console.nextInt();
15
16 List<Integer> primes = sieve(max);
17 System.out.println("Prime numbers up to " + max + ":");
18 System.out.println(primes);
19 }
20
21 // Returns a list of all prime numbers up to given max
22 // using the sieve of Eratosthenes algorithm.
23 public static List<Integer> sieve(int max) {
24 List<Integer> primes = new LinkedList<Integer>();
25
26 // add all numbers from 2 to max to a list
27 List<Integer> numbers = new LinkedList<Integer>();
28 for ( int i = 2; i <= max; i++) {
29 numbers.add(i);
30 }
31
32 while (!numbers.isEmpty()) {
33 // remove a prime number from the front of the list
34 int front = numbers.remove(0);
35 primes.add(front);
36
37 // remove all multiples of this prime number
38 Iterator<Integer> itr = numbers.iterator();
39 while (itr.hasNext()) {
40 int current = itr.next();
41 if (current % front == 0) {
42 itr.remove();
43 }
44 }
45 }
46
47 return primes;
48 }
49 }