This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 74

Primality testing through perfect hashing

Due: March 29
Points: 5

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.