Problem 95

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:

- Store all these prime numbers in a Bloom filter instead of a perfect hash table.
- Use the Miller-Rabin algorithm

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.