Paul NgugiLoops are fundamental in programming. The ability to write loops is essential in learning Java programming. If you can write programs using loops, you know how to program!
Finding the Greatest Common Divisor
The greatest common divisor (gcd) of the two integers 4 and 2 is 2. The greatest common divisor of the two integers 16 and 24 is 8. How would you write this program to find the greatest common divisor? Would you immediately begin to write the code? No. It is important to think before you code. Thinking enables you to generate a logical solution for the problem without concern about how to write the code.
Let the two input integers be n1 and n2. You know that number 1 is a common divisor, but it may not be the greatest common divisor. So, you can check whether k (for k = 2, 3, 4, and so on) is a common divisor for n1 and n2, until k is greater than n1 or n2. Store the common divisor in a variable named gcd. Initially, gcd is 1. Whenever a new common divisor is found, it becomes the new gcd. When you have checked all the possible common divisors from 2 up to n1 or n2, the value in variable gcd is the greatest common divisor. Once you have a logical solution, type the code to translate the solution into a Java program as follows:
int gcd = 1; // Initial gcd is 1
int k = 2; // Possible gcd
while (k <= n1 && k <= n2) {
if (n1 % k == 0 && n2 % k == 0)
gcd = k; // Update gcd
k++; // Next possible gcd
}
// After the loop, gcd is the greatest common divisor for n1 and n2
The program prompts the user to enter two positive integers and finds their greatest common divisor.
Translating a logical solution to Java code is not unique. For example, you could use a for loop to rewrite the code as follows:
for (int k = 2; k <= n1 && k <= n2; k++) {
if (n1 % k == 0 && n2 % k == 0)
gcd = k;
}
A problem often has multiple solutions, and the gcd problem can be solved in many ways.
Case Study: Predicting the Future Tuition
Suppose that the tuition for a university is $10,000 this year and tuition increases 7% every year. In how many years will the tuition be doubled?
Before you can write a program to solve this problem, first consider how to solve it by hand. The tuition for the second year is the tuition for the first year * 1.07. The tuition for a future year is the tuition of its preceding year * 1.07. Thus, the tuition for each year can be computed as follows:
double tuition = 10000; int year = 0; // Year 0
tuition = tuition * 1.07; year++; // Year 1
tuition = tuition * 1.07; year++; // Year 2
tuition = tuition * 1.07; year++; // Year 3
...
Keep computing the tuition for a new year until it is at least 20000. By then you will know how many years it will take for the tuition to be doubled. You can now translate the logic into the following loop:
double tuition = 10000; // Year 0
int year = 0;
while (tuition < 20000) {
tuition = tuition * 1.07;
year++;
}
The complete program is shown below:
The while loop (lines 8-11) is used to repeatedly compute the tuition for a new year. The loop terminates when the tuition is greater than or equal to 20000.
Case Study: Converting Decimals to Hexadecimals
Hexadecimals are often used in computer systems programming. How do you convert a decimal number to a hexadecimal number? These hexadecimal digits can be found by successively dividing d by 16 until the quotient is 0. The hexadecimal digits include the
decimal digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, plus A, which is the decimal value 10; B, which is the decimal value 11; C, which is 12; D, which is 13; E, which is 14; and F, which is 15.
For example, the decimal number 123 is 7B in hexadecimal. The conversion is done as follows. Divide 123 by 16. The remainder is 11 (B in hexadecimal) and the quotient is 7. Continue divide 7 by 16. The remainder is 7 and the quotient is 0. Therefore 7B is the hexadecimal number for 123. The program prompts the user to enter a decimal number and converts it into a hex number as a string.
The program prompts the user to enter a decimal integer (line 12), converts it to a hex number as a string (lines 15–25), and displays the result (line 27). To convert a decimal to a hex number, the program uses a loop to successively divide the decimal number by 16 and obtain its remainder (line 18). The remainder is converted into a hex character (lines 21). The character is then appended to the hex string (line 23). The hex string is initially empty (line 15). Divide the decimal number by 16 to remove a hex digit from the number (line 24). The loop ends when the remaining decimal number becomes 0.
The program converts a hexValue between 0 and 15 into a hex character. If hexValue is between 0 and 9, it is converted to (char)(hexValue + '0') (line 21). Recall that when adding a character with an integer, the character’s Unicode is used in the evaluation. For example, if hexValue is 5, (char)(hexValue + '0') returns 5. Similarly, if hexValue is between 10 and 15, it is converted to (char)(hexValue - 10 + 'A') (line 21). For instance, if hexValue is 11, (char)(hexValue - 10 + 'A') returns B.
Case Study: Checking Palindromes
This section presents a program that checks whether a string is a palindrome. A string is a palindrome if it reads the same forward and backward. The words “mom,” “dad,” and “noon,” for instance, are all palindromes.
The problem is to write a program that prompts the user to enter a string and reports whether the string is a palindrome. One solution is to check whether the first character in the string is the same as the last character. If so, check whether the second character is the same as the second-to-last character. This process continues until a mismatch is found or all the characters in the string are checked, except for the middle character if the string has an odd number of characters. Here's the program:
The program uses two variables, low and high, to denote the position of the two characters at the beginning and the end in a string s (lines 15, 18). Initially, low is 0 and high is s.length() – 1. If the two characters at these positions match, increment low by 1 and decrement high by 1 (lines 26–27). This process continues until (low >= high) or a mismatch is found (line 22).
The program uses a boolean variable isPalindrome to denote whether the string s is palindrome. Initially, it is set to true (line 20). When a mismatch is discovered (line 22), isPalindrome is to false (line 23) and the loop is terminated with a break statement (line 24).
Case Study: Displaying Prime Numbers
This section presents a program that displays the first fifty prime numbers in five lines, each containing ten numbers.
An integer greater than 1 is prime if its only positive divisor is 1 or itself. For example, 2, 3, 5, and 7 are prime numbers, but 4, 6, 8, and 9 are not.
The problem is to display the first 50 prime numbers in five lines, each of which contains ten numbers. The problem can be broken into the following tasks:
- Determine whether a given number is prime.
- For number = 2, 3, 4, 5, 6, . . ., test whether it is prime.
- Count the prime numbers.
- Display each prime number, and display ten numbers per line.
Obviously, you need to write a loop and repeatedly test whether a new number is prime. If the number is prime, increase the count by 1. The count is 0 initially. When it reaches 50, the loop terminates.
Here is the algorithm for the problem:
Set the number of prime numbers to be printed as
a constant NUMBER_OF_PRIMES;
Use count to track the number of prime numbers and
set an initial count to 0;
Set an initial number to 2;
while (count < NUMBER_OF_PRIMES) {
Test whether number is prime;
if number is prime {
Display the prime number and increase the count;
}
Increment number by 1;
}
To test whether a number is prime, check whether it is divisible by 2, 3, 4, and so on up to number/2. If a divisor is found, the number is not a prime. The algorithm can be described as follows:
Use a boolean variable isPrime to denote whether
the number is prime; Set isPrime to true initially;
for (int divisor = 2; divisor <= number / 2; divisor++) {
if (number % divisor == 0) {
Set isPrime to false
Exit the loop;
}
}
The complete program is given below:
public class PrimeNumber {
public static void main(String[] args) {
final int NUMBER_OF_PRIMES = 50; // Number of primes to display
final int NUMBER_OF_PRIMES_PER_LINE = 10; // Display 10 per line
int count = 0; // Count the number of prime numbers
int number = 2; // A number to be tested for primeness
System.out.println("The first 50 prime numbers are \n");
// Repeatedly find prime numbers
while(count < NUMBER_OF_PRIMES) {
// Assume the number is prime
boolean isPrime = true; // Is the current number prime?
// Test whether number is prime
for(int divisor = 2; divisor <= number / 2; divisor++) {
if(number % divisor == 0) { // If true, number is not prime
isPrime = false; // Set isPrime to false
break; // Exit the for loop
}
}
// Display the prime number and increase the count
if(isPrime) {
count++; // Increase the count
if(count % NUMBER_OF_PRIMES_PER_LINE == 0) {
// Display the number and advance to the new line
System.out.println(number);
}
else
System.out.print(number + " ");
}
// Check if the next number is prime
number++;
}
}
}
The first 50 prime numbers are
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 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
This is a complex program for novice programmers. The key to developing a programmatic solution for this problem, and for many other problems, is to break it into subproblems and develop solutions for each of them in turn. Do not attempt to develop a complete solution in the first trial. Instead, begin by writing the code to determine whether a given number is prime, then expand the program to test whether other numbers are prime in a loop.
To determine whether a number is prime, check whether it is divisible by a number between 2 and number/2 inclusive (lines 19-24). If so, it is not a prime number (line 21); otherwise, it is a prime number. For a prime number, display it. If the count is divisible by 10 (lines 30-33), advance to a new line. The program ends when the count reaches 50.
The program uses the break statement in line 22 to exit the for loop as soon as the number is found to be a nonprime. You can rewrite the loop (lines 19-24) without using the break statement, as follows:
for (int divisor = 2; divisor <= number / 2 && isPrime;
divisor++) {
// If true, the number is not prime
if (number % divisor == 0) {
// Set isPrime to false, if the number is not prime
isPrime = false;
}
}
However, using the break statement makes the program simpler and easier to read in this case.
