Lab 5: Arrays

This weeks labs will focus on arrays in Java.

Introduction

Arrays are one of the most fundamental data structures, and they are incredibly useful. One reason they are so handy is that it is possible to access a slot using a computed-at-runtime integer - this is a sharp contrast to non-array variables where you have to know the name of the variable you want to access at compile time. Furthermore, the length of the array can also be determined at runtime - again, a contrast to non-array variables where you have to declare each one and thus must decide on the number of them by compile time.

Setup

Create a lab05 directory in your cs124 directory to hold the files for this lab.

Copy the files from /classes/s07/cs124/labs/lab05/ to your lab05 directory.

Exercises

Here are the exercises for this week's lab, due next Thursday.

Write a program called ReadNums.java to read in integers from the user until the user enters a number less than 0, and then print those integers to the screen. If the user enters 1000 integers (an unlikely event), then your program can stop and print the integers to the screen. Note that you cannot print the integers out as the user enters them, instead you must read all the integers in and then print them all out. Below is an example run (user input is in bold):
```
Enter a sequence of numbers >= 0.  Enter a negative number to stop.  You may enter at most 1000 numbers.

Enter number: 5
Enter number: 2
Enter number: 12
Enter number: -1

You entered:
5
2
12
```

Write a program called PrintMatrix.java that reads in 9 integers from the user and then prints them out in a 3x3 matrix. It should also print out the sum of each row and column. Below is an example run (user input is in bold):

Enter number 1: 8
Enter number 2: 3
Enter number 3: 9
Enter number 4: 0
Enter number 5: 10
Enter number 6: 3
Enter number 7: 5
Enter number 8: 17
Enter number 9: 1

Matrix:
Row 1: 8 3 9
Row 2: 0 10 3
Row 3: 5 17 1

Row totals: 20 13 23
Column totals: 13 30 13

A prime number is a number which is only (evenly) divisible by itself and 1. The Sieve of Eratosthenes is a famous algorithm for finding prime numbers. To use the sieve, write down all of the numbers from 2 to some number N and then apply the following algorithm:
```
  for each number from 2 to N do
    if the number hasn't been crossed off,
      it is a prime
      cross off all multiples of that number  
```
As an example, let's use the sieve to find the prime numbers between 2 and 15. We start with all the numbers listed:

2 3 4 5 6 7 8 9 10 11 12 13 14 15

Begin with 2 - it hasn't been crossed off, so 2 is the first prime and we cross off all the multiples: (bold indicates primes; gray background marks numbers crossed off)

2 3 4 5 6 7 8 9 10 11 12 13 14 15

Now we move on to the next number, 3. It hasn't been crossed off, so it is a prime and we cross off all numbers which are multiples of 3:

2 3 4 5 6 7 8 9 10 11 12 13 14 15

The next number (4) has been crossed off so we do nothing. The next number (5) hasn't been crossed off, so it is prime and we cross off all multiples of 5:

2 3 4 5 6 7 8 9 10 11 12 13 14 15

This process repeats: 6 has been crossed off, so we do nothing. 7 hasn't, so it is prime and we cross off all multiples of 7:

2 3 4 5 6 7 8 9 10 11 12 13 14 15

8, 9, 10 have all been crossed off, so 11 is the next prime. And so forth...

An array can be very handy for implementing this algorithm. The idea is to use an array of booleans to keep track of what numbers have and haven't been crossed off. We'll use a value of true in slot k to indicate that the number k hasn't been crossed off, and a value of false to indicate that the number has been crossed off. At the beginning all of the slots are initialized to true. Now, apply the algorithm above starting with slot 2 - if the number hasn't been crossed off, then the value stored in its slot is true; crossing off a number means setting the value in the appropriate slot to false. (The values in slots 0 and 1 will never be used.)

Your task is to write a program called FindPrimes.java to find prime numbers using the Sieve of Eratosthenes, using a boolean array as outlined above. The program should prompt the user for a number N which is the upper end of the range, and should then print all of the prime numbers between 2 and N (including N if it is prime). Make sure your array is large enough to have a slot numbered N.

Handin

Verify that your lab05 folder contains all of the files you created or modified for this lab, then copy your entire lab05 folder to the handin directory ~mcorliss/handin/124/username (where username is replaced with your username).