This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
Write a program that uses a perfect hash table to test for prime numbers less than one million.
Your program must first generate all the prime numbers less than one million. This sequence starts with 2, 3, 5, 7, ... and ends with 999961, 999979, 999983, and in all there are exactly 78,498 prime numbers less than one million.
(There are a multitude of ways to generate all these prime numbers; the fastest way to do it, which is not too complicated, would probably be to use the Sieve of Eratosthenes.)
After generating the entire list of prime numbers, you need to insert them into a 2-level hash table using the idea of "perfect hashing" that we went over in class. You will choose the hash functions randomly to guarantee that the total size is \(O(n)\) and there are zero collisions on the 2nd level, making each lookup operation cost only \(O(1)\).
After your program generates the prime numbers and creates the 2-level hash table, it should read in integers from the user, one at a time, and look up each number in the hash table. If it's there, your program should report that the number is prime, and otherwise it should report "composite".
Submit your program according to the instructions on the submit page.