HashSet Data Structure

The HashSet is a Set class in Java that uses a hash table internally. The HashSet is able to add, find and remove items in constant time, so it can solve many problems in an optimal manner. (Ruby and Python provide the same capabilities with their Set classes.)

A HashSet is a good choice whenever you have a large set of items and need to quickly check if a given item is in the set or not. We already saw that this can be used to detect duplicate data as you go through a list of numbers. It is often used to check live user data against established data for matches. For example, a Spell Checker that checks words as a user types them needs to extremely fast, so it uses a HashSet of real words to check if a given word is real or not. Here's a list of different cases where a HashSet could be used:

When not to use a HashSet

While a HashSet is great for quickly looking up items, sometimes other data structures are a better choice. For example, let's say you were implementing an autocomplete feature to suggest searches as a user types. To do this with a HashSet, you would need to store every prefix of a search as a separate entry, which would waste a lot of memory. For such cases, the Trie is a better choice of data structure.

Challenge

Given a list of numbers, count and print the number of prime numbers in the list. (A prime number is a number with no factors besides 1 and itself.)

Sample Input

1
5
2 3 5 6 9

Sample Output

3

There are 3 prime numbers in the input: 2 3 5.

Constraints

All the numbers will be from 2 to 10,000.

Guideline

Create a Set of prime numbers less than 10,000. There are 2 ways you can do this:

• Use the Sieve of Eratosthenes, then create a set of the prime numbers from your sieve.
• Google it to find the values, hard-code an array with those numbers, and then copy the array values to a Set.

Once you have this Set, the next part is easy.