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

The following is a sample log of execution of the program:
This program will tell you all prime
numbers up to a given maximum.
Maximum number? 50
Prime numbers up to 50:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Our version of the sieve algorithm has been simplified. The real algorithm stops
when the first element of the numbers list is greater than the square root of the maxi-
mum, because any number this large that remains in the list cannot have any multi-
ples remaining in the list. For example, when the maximum is 25, once the item at
the front of the numbers list exceeds 5, all remaining numbers in the list are known
to be prime and can be placed in the primes list.
The algorithm can be improved in other ways. For example, the initial list of num-
bers doesn't need to store every integer from 2 through the maximum. It can instead
store 2 and each odd integer up to the maximum, because no other even numbers are
prime. This modification makes the algorithm more efficient because fewer numbers
need to be processed. These two improvements to the algorithm are left as an exercise.
11.2 Sets
A major limitation of both linked and array lists is that searching them takes a long
time. Generally, if you want to search a list, you have to look at each element
sequentially to see whether you've found the target. This can take a long time for a
large list.
Another limitation of lists is that it's not easy to prevent a list from storing dupli-
cate values. In many cases this isn't a problem, but if, for example, you are storing
a collection to count the number of unique words in a book, you don't want any
duplicates to exist. To prevent duplicates in a list, you have to sequentially search the
list every time you add to it, in order to make sure you aren't adding a word that's
already present.
When you want to maintain a collection of elements that can be searched quickly and
that prevents duplicates, you're better off using another abstract data type called a set.
Set
A collection that cannot contain duplicates.
The Set collection is very much like the mathematical notion of a set. Sets do not
support all the operations you can perform on lists (namely, any operation that
requires an index), but they do offer the benefits of fast searching and effortless elim-
ination of duplicates.