CS 206: Data Structures
Exercise#9

Due on Thurssday, March 6

 

In this exercise, we will make use of our List ADT (not the fixed size version) to do an experiment about prime numbers. Prime numbers are extremely useful in encryption (especially is everyday situations when you are communicating with someone over the internet, or purchasing from a web site). There are lots of interesting properties about prime numbers, but we will restrict ourselves to exploring some simple, yet non trivial explorations about prime numbers. Here are some simple questions worth answering:

  1. How many prime numbers are there betwen 1 and 100?
  2. How many prime numbers are there between 10,000 and 100,000?
  3. What is the smallest prime number between 10,000 and 100,000?
  4. What is the largest prime number between 10,000 and 100,000?

Write a Java applet that inputs two numbers (say N1 and N2) and generates all the prime numbers between N1 and N2 and stores them in a List and informs the user as to how many primes were found. The user can then ask for all the numbers to be printed. The user can also ask for a specific number to be retrieved (for example, what is the 0th prime number? Or the 453rd prime number? etc.).

Using this applet, you should try and determine the answer to the following:

  1. How many primes are there between 1 and 1,000,000? What is the largest prime in this group? What is the 42nd prime in this group?
  2. How many primes are there between 9,000,000 and 10,000,000? What is the smallest prime in this group? What is the largest prime in this group? What is the 42nd prime in this group?
  3. Use your program to explore some other interesting property of prime numbers. For example, what is the largest prime number you can find using your program?

Bring the answers to the above questions to class on thursday (based on the outputs of your program). Please do not discuss the answers with anyone else. The exercise, over and beyond learning to use the List ADT implementations, is also designed to ensure that you have complete confidence in the correctness of your algorithms, and their implementations. We will perform a comparison of results in class.

You will not hand in anything other than the answers to the above questions. I.e., there is no need to hand in the Java program. If needed, Deepak will be happy to sit with you and look at your program and make suggestions for improvement.

Back to CS206 Course Materials