This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
Problem 94 asks you to build a perfect static hash table that stores all prime numbers less than 1 million. This can be used to quickly test whether any integer less than 1 million is prime.
Compare this method of primality testing to the following two other ideas that would accomplish the same thing:
When I say "compare", I mean give the relative strengths and weaknesses of each approach. The things you might consider are time, memory, and the probability of getting the right answer.