Java Lab Manual
Purpose of this lab session
In this lab you will print a table using a single loop. In addition, nested loops are an important tool in programming. Some tables can be printed using a nested loop but, there are many other uses. Since you can't write a nested loop unless understand how it is executed, you will practice doing a walk through of some nested loops.
To prepare for this lab
§ Read Wu: Chapter 6
§ Read through this laboratory session
§ Using your memory device, copy the files Primes.java and NestedLoops.java from http://www.mscs.mu.edu/~marian/60/Labs/lab10
To Complete this lab
§ This is an individual lab. You may ask the lab tutor for help and you may consult with your neighbor if you are having difficulties.
§ In this lab, you will modify the and add to the two copied programs. When done with each program, do a final run of each program and place a copy of the printed output in each file.
§ When you have completed the lab, hand in your printouts to the lab tutor.
10.1 Finding Prime Numbers
The positive factors, or divisors, of 2 are 1 and 2 .
The positive factors, or divisors, of 6 are 1, 2, 3, and 6.
The positive factors, or divisors, of 9 are 1, 3 and 9.
Step 1: List the factors of 7 ______
List the factors of 12 ______
List the factors of 13 ______
List the factors of 49 ______
Defintion: A prime number is a positive integer that has two distinct factors, 1 and itself.
The number one is not a prime number since it does not have two distinct factors. The number two is the smallest prime number and the only even number that is a prime.
Circle the numbers that are prime numbers:
-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
int number, is divisible by int divisor if number % divisor == 0.
For example: since 12 % 4 == 0 is true, 12 is divisible by 4
since 12 % 5 == 0 is false, 12 is not divisible by 5
Therefore, to determine if a positive integer number is a prime number, check if any of the integers between 2 and (number – 1) are divisors, or factors, of number.
The following algorithm, described using pseudocode, determines if int number is a prime number.
assume boolean isPrime = true
for factor between values of 2 and (number -1)
if (number % divisor == 0)
isPrime = false
Notice the following about the above pseudocode:
§ begin by assuming that num is a prime number: boolean isPrime = true;
§ Since all numbers are divisible by 1 and by themselves, only the numbers between 2 and (number – 1) are checked for divisibility into number
§ once a factor of num is found, isPrime is false and the existence of additional divisors is irrelevant.
Step 1:Open the file Primes.java and read it for understanding.
class Primes
{
public static void main(String[] args)
{
int number = -1;
do
{
System.out.println(number + " is a prime is " +
Primes.isPrime(number));
number++;
}while(number < 26);
}
private static boolean isPrime(int number)
{
return false;
}
}
The method
private static boolean isPrime(int number)
returns true if number is a prime number and false otherwise. In order for the above file to compile, the dummy method isPrime must return a boolean value, I chose false.
Compile and run the program. For which of the test numbers is true printed?
______
______
Step 2: Let's begin to write the isPrime method. Initially, we assume number is a prime number by assigning true to isPrime. If number is less than two, false is assigned to isPrime. If number is greater than two, a loop that tries to find a divisor of number is needed. Notice that it is not necessary to explicitly check if number is equal to two since isPrime is initially set to true and will not be changed. Revise the isPrime method as shown
private static boolean isPrime(int number)
{
boolean isPrime = true;
if(number < 2)
isPrime = false;
else if(number > 2)
{
//look for a divisor of number
//if a divisor is found, set isPrime to false
}
return isPrime;
}
Compile and run the program. For which of the numbers tested in the main method, does isPrime return true?
______
______
Step 3: Add the loop that looks for a divisor of number. When a divisor is found, isPrime is set to false and, for efficiency, the loop should stop. When a break statement is executed inside of a loop, the loop terminates and the next statement following the loop is executed.
private static boolean isPrime(int number)
{
boolean isPrime = true;
if(number < 2)
isPrime = false;
else if(number > 2)
{
for(int divisor = 2; divisor < number; divisor++)
{
if(number % divisor == 0)
{
isPrime = false;
break;
}
}
}
return isPrime; //when the loop ends, isPrime is returned
}
Compile and run the program. For which of the numbers tested in the main method, does isPrime return true?
______
______
We now have a working method. However, that does not mean that we are done. You should always re-read your code to see if improvements can be made to its appearance, its readability, its logic or its efficiency. What improvements can be made to the isPrime method?
§ Since two is the only even prime number, we could make a special case for even numbers, so that only odd numbers are checked by the loop.
§ If the loop no longer needs to check for divisibility by two, it no longer needs to check for divisibility by any other even number. That is, we only need to check for divisibility by the odd numbers 3, 5, 7, ...
§ The number 53 is a prime number. How many possible divisors must be checked. Do we need to check all of the odd numbers between 3 and 52, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 24, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, and 51? The answer is no, but where can we stop?
The factors of 36, are 1, 2, 3, 4, 6, 9, 12, 18 and 36. Note:1 x 36 = 36
2 x 18 = 36
3 x 12 = 36
4 x 9 = 36
6 x 6 = 26 / The factors of 49, are 1, 7 and 49. Note:
1 x 49 = 49
7 x 7 = 49 / Note that for each example, half of the factors are greater than the square root and the other half are less than the
square root.
In addition, if a divisor of the number (other than 1 or itself) does exist, the loop will find the smaller number in the pair of factors first. This is sufficient to determine that the number is not prime.
Step 4: Revise the isPrime method to reflect the suggested improvements.
private static boolean isPrime(int number)
{
boolean isPrime = true;
if(number < 2)
isPrime = false;
else if(number > 2)
{
if(number % 2 == 0) //even numbers are not prime
isPrime = false;
else
{
double sqrt = Math.sqrt(number); //evaluate once
for(int divisor = 3; isPrime & divisor <= sqrt; divisor += 2)
{
if(number % divisor == 0)
isPrime = false; //break has been removed
}
}
}
return isPrime;
}
Compile and run the program. For which of the numbers tested in the main method, does isPrime return true?
______
______
Step 5: Note that the only values stored in number that allow the code
for(int divisor = 3; isPrime & divisor <= sqrt; divisor += 2)
{
if(number % divisor == 0)
isPrime = false;
}
to execute are odd. Use a table of values to do a walk through of the loop.
number = 125, sqrt ≈ 11.18 / number = 53, sqrt ~ 7.28What condition makes the loop end when number = 125?
______
______
What condition makes the loop end when number = 53?
______
______
10.2 printing a chart
A loop can be used to print a chart of values. For example, this chart contains all of the prime numbers between 1 and 150.
Primes Between 1 and 150
2 3 5 7 11 13
17 19 23 29 31 37
41 43 47 53 59 61
67 71 73 79 83 89
97 101 103 107 109 113
127 131 137 139 149
There are 35 primes between 1 and 150
Begin by analyzing what is printed.
Print the heading
For every number between 1 and 150, if the number is a prime number, print it.
Print the footer
Step 6: Add the following to Primes.java
In the main method, comment out the existing statements and add the single statement
printPrimeChart(1, 150);
Outside of the main method, add a third method to the Primes class
public void printPrimeChart(int min, int max)
{
System.out.println(" Primes Between " + min + " and " + max + "\n");
for(int num = min; num <= max; num++)
{
if(isPrime(num))
{
System.out.print(num + " ");
}
}
System.out.println("\n\n" +
"There are " + count + " primes between " + min + " and " + max);
}
Compile and run the program. Is the expected chart printed as planned? Explain the problem.
______
______
______
______
Step 7: Obviously, we need to print newline characters to force new rows. In many charts, every calculated value is printed and the placement of the newline character is determined by the loop counter, num. However, in the prime chart, not all values of num are printed. Therefore, another criteria is needed to determine when the newline character should be printed.
If six columns of numbers are desired, a newline character will be printed after the sixth, twelfth, eighteen, twenty-fourth, etc. primes are printed. If we introduce a separate counter that is incremented every time a prime number is printed, then a newline character is printed when the counter is 6, 12, 18, 24, . . . These values all have something in common – they are divisible by 6.
Modify the printPrimeChart method to incorporate the needed changes.
public static void printPrimeChart(int min, int max)
{
int counter = 0; // determines when a newline character is printed.
System.out.println(" Primes Between " + min + " and " + max + "\n");
for(int num = min; num <= max; num++)
{
if(isPrime(num))
{
System.out.print(num + " ");
count++;
if(count % 6 == 0) // if count is divisible by 6
{ // print a newline character
System.out.println();
}
}
}
System.out.println("\n\n" +
"There are " + count + " primes between " + min + " and " + max);
}
Compile and run the program. Does the chart print as planned? Explain any problems in the appearance.
______
______
______
______
Step 8: Before we handle the alignment problem in our chart, change the code to print seven columns of prime numbers instead of six. Add another call to printPrimeChart in main to print prime numbers between 999,000 and 1,000,000.
Compile and run the program. What is the largest prime number less than 1,000,000? How many prime numbers are between 999,000 and 1,000,000?
______
______
______
10.3 String Alignment
The problem with the current printPrimeChart is that the numbers are not aligned in columns. Columns can be aligned to the left or right easily using some of the new features added to Java 1.5. The following have all been added to Java 5:
· To the java.io.PrintStream class (System.out is a PrintStream object), a new method
public PrintStream printf(String format, Object ... args)
· To the java.lang.String class, a new method
public static String format(Stringformat, Object...args)
· A new class java.util.Formatter which contains a method
Formatter format(Stringformat, Object...args) Writes a formatted string to this object's destination using the specified locale, format string, and arguments.
All of these options have much more versatility that we need for our prime chart or than we care to discuss here. If you would like to read the online documentation, I suggest that you begin with the Formatter class. For now, we will use the printf method.
Step 9: Now, call the printf method from the printPrimeChart method, by replacing the statement
System.out.print(num + " ");
with the statement
System.out.printf("%10d", num);
that right aligns each integer value ("%d") in a field-width of ten.
Compile and run the program. Record any alignment problems.
______
______
Step 10: To left align each number in field-width of ten, place a negative sign in before the 10 in the statement
System.out.printf("%-10d", num);
Compile and run the program. Record any alignment problems.
______
______
10.4 Nested Loops
Suppose that we want to write a method to print a rectangle of characters with a variable width and height with header
void printRectangle(int rows, int columns, char symbol)
For example, the call
printRectangle(3, 5, '?');
should print
?????
?????
?????
We could begin by forming the string "?????" and then print the string three times. For example, the loop
String s = "";
for(int c = 1; c <= columns; c++)