CS 1713/1711 Introduction to Computer Science Laboratory 8

CS 1711 Recitation Laboratory 8:
Arrays [11/2/99; 11/4/99]

Objectives:

Learn to use arrays.
Have more extensive practice with loops.
Write an initialization function to perform activities common to constructor and modifiers.

Check-off procedure:

You must attend the recitation and sign in. This laboratory will be checked off using the new procedures.

Laboratory details:

A prime number is a positive integer that is only divisible by itself and by 1. In this laboratory you will implement a Primes class using a sieve. The Primes class has a constructor that takes a single integer parameter, upper, specifying the upper bound of the numbers to be considered. The numbers in [0, upper] are in the range of the sieve. The class has accessor methods to:

return the m-th prime number or -1 if the m-th prime number is not in the range handled by the sieve.
return the number of primes between 2 and n or -1 if n is not in the range handled by the sieve.
return a boolean value indicating whether integer n is prime. (Note: return false if n is not in range. This issue will be addressed in the second part of the assignment.)
return the value of upper.
print the primes in the interval [0, upper].

There are many ways to calculate primes. In this laboratory is you will implement a sieve to practice with arrays. To analyze the distribution of prime numbers between 1 and upper, you will create a boolean array of length upper + 1 (the sieve) and initialize all of the entries to true. For each integer between 2 and the square root of upper, you will mark entries corresponding to the multiples of that integer to false. When you are finished the sieve will contain true only at entries which were not multiples of other integers (e.g. primes). For example, when upper is 15, the array starts out:

   Entry:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
   Value:  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T

After multiples of 2 are taken out, the array is:

   Entry:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 
   Value:  T  T  T  T  F  T  F  T  F  T  F  T  F  T  F  T

After multiples of 3 are taken out, the array is:

 
   Entry:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  
   Value:  T  T  T  T  F  T  F  T  F  F  F  T  F  T  F  F

Handling 1 and 0, we are done:

 
   Entry:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15   
   Value:  F  F  T  T  F  T  F  T  F  F  F  T  F  T  F  F

Exercise I: The basic sieve.

Preliminaries:
- Create a standalone project called PrimesTestMain.
- Create a file called Primes.java containing the skeleton of the Primes class.
- Fill in the constructor accessor methods as specified above as skeletons. Since accessors must return a value, you can have the int return values be 0 and the boolean values be true.
- Write test statements in the main program to instantiate a Prime object of length 15 and output the number of primes (0 so far).
- Build and run the program.
Add the sieve:
- Add a private field, myUpper specifying the size of the sieve.
- Add a private field, mySieve, to the Primes class definition. mySieve is an array of boolean values of size [0, myUpper + 1].
- Write an initializeSieve helper function that sets mySieve to be a boolean array of size myUpper + 1 that contains true values in the entries corresponding to primes and false otherwise.
- Call the initializeSieve function in the constructor to initialize mySieve and possibly other related fields.
- Implement the printPrimes accessor method to print the prime numbers between 0 and myUpper.
- Add test statements to the main program to check to see that the sieve has been implemented correctly.
Full implementation: Add the implementation of the remaining accessor methods as specified above. Add test statements to test the program.

Exercise II: Resizing the sieve

In this section you will add a modifier method called resize that takes a single integer parameter newsize. If newsize is is equal to the current value of myUpper, don't do anything. If newsize is not equal to the current value of myUpper, adjust the fields of Primes to handle primes in [0, newsize].

Exercise III: Automatic resizing

The accessor methods for Primes only work if the value is less than myUpper. Add code to the method that indicates whether or not n is prime to resize the sieve appropriately if n > myUpper. Hint: use initializeSieve. Is this method still just an accessor? The other accessor methods of Primes could be modified in a similar way, but this is not required for the assignment.

Last revision: October 31, 1999 at 5:40 am.