5.7 Programming with Methods

One of the primary reasons for having methods in programming languages is to make it easier to solve complex problems. Having discussed how to create methods, we are now going to look at how we might use methods to create a solution to problems larger than those we have examined previously.

To illustrate the use of methods in problem-solving, we will consider a problem related to one proposed by the mathematician Christian Goldbach in 1742, in a letter to Leonhard Euler. In the letter, he made the suggestion that has since come to be known as Goldbach's Conjecture. It states that every even number greater than two can be expressed as the sum of two prime numbers/. Despite the work of many number theorists over the years and even the posting of a $1 000 000 prize for a proof, the conjecture is still unproven (at the time that this was written). Although it has been impossible to prove that the conjecture is true for every even number, it is not too difficult to check the conjecture for a given even number and that is the problem that we are going to examine here.

Specifically, we want to develop a program that will repeatedly prompt the user for positive even integer values greater than two and attempt to write each of those numbers as the sum of two primes. The program should continue to read values until the user supplies input of zero. Invalid input should be rejected gracefully.

To begin, let us try to develop a strategy. For the moment, we are going to avoid worrying about the details of the program and only focus on its main structure. We want the program to repeatedly read values and, for each value read, see whether or not it satisfies the conjecture. We can refine this analysis into something that looks more like Java (or many other computer languages). Such a form is sometimes called pseudo-code.

Example 1

A pseudo-code solution to the problem of testing the validity of Goldbach's Conjecture might take the following form.

get first value from user

while (value != 0)

2A prime number is a positive integer that has exactly two distinct factors: one and the number itself.

{

test Goldbach's Conjecture on value

get next value from user

}

The pseudo-code provides the basis for a main method in our solution to the problem. Some lines of the pseudo-code can be converted directly into single lines in the Java language; others require a number of statements. For the latter type, we can write methods. Thinking this way, we can write the main method.

Example 2

The pseudo-code of the previous example can be converted to Java as the following main method.

public static void main (String[] args)

{

int value = nextNumber();

while (value != 0)

{

testGoldbach(value);

value = nextNumber();

}

}

Having designed an overall strategy for the solution, we can now focus on the parts that have not yet been analyzed in detail. Here there are two parts that need expansion: the method next Number that reads values and the method testGoldbach that tests the conjecture for a given even number.

The method next Number should prompt a user for a value and read a value, rejecting invalid input from the user. The next example shows a possible implementation of this method.

Example 3

The method nextNumber forces a user to supply a non-negative even number as input. Since the method is only going to be used within this program, we have made its visibility private so that it cannot be called from outside the class in which it is defined.

private static int nextNumber ()

{

int response;

do

{

System.out.println("Give an even integer> 2 ”

+ "(0 to stop) ”);

response = In.getlnt();

}

while (response<O || response%2!=O || response==2);

return response;

}

The method testGoldbach should test the conjecture for a given even number, n, and print either two primes whose sum is n or a message that the conjecture is not true. To see how we might solve the problem in general, it might be useful first to see how we might proceed with a particular case. We do this in the next example.

Example 4

To determine whether or not the value 12 satisfies Goldbach's Conjecture, we must try to find two primes that sum to 12. To do so, we can break 12 into two parts in various ways, using increasingly larger primes as the first part of the number and testing the differences between these primes and 12 to see if they are also primes. The smallest prime is two, so we start there. The table summarizes our search.

If we had not had success on the third try, the next pair that we would have tried would have been 7 and 5 but there would be no need to do so because we would have already examined 5 and 7. Thus, once our first part has reached half way to the value being examined, we can quit. If no pair of primes has been found at this point, Goldbach's Conjecture must be false.

We incorporate the ideas of Example 4 in our general solution to the problem of testing Goldbach's Conjecture for any given positive even number n. We repeatedly break n up into two parts. The first part should be prime and no more than half the value read. We then test the second part to see if it is also prime. If it is, then the conjecture is true for this value. If not, we continue to look for other possibilities until we find a satisfactory pair of values or we have tried all possible primes for the first part. If we never find a pair that works, then we conclude that the conjecture is false. The next example expresses this in pseudo-code.

Example 5

A pseudo-code solution to the problem of testing Goldbach's Conjecture for a positive even integer n could take the following form.

firstPart = 2

while (conjecture not verified or rejected)

{

secondPart = n - firstPart

if (secondPart < firstPart)

conjecture is false: print message

else if (secondPart is prime)

we have verified the conjecture: print parts

else

firstPart = next prime after current firstPart

}

Number theory tells us that there are infinitely many primes so that we can always find a next prime after the current first part. This ensures that the assignment in the last line of code will always be successful.

We can now convert the pseudo-code to a Java method.

Example 6

The following Java method tests a positive even integer to see if it satisfies Goldbach's Conjecture. The loop is controlled by a boolean flag done that is initially set to false. It is made true if the conjecture is either verified or refuted. The method assumes that n is a positive even integer greater than two, a condition that is assured by the method nextNumber.

private static void testGoldbach (int n)

{

int firstPart = 2;

boolean done = false;

while (! done)

{

int secondPart n - firstPart;

if (secondPart < firstPart)

{

System.out.println("Goldbach's Conjecture is “

+ "false - it fails for II + n);

done = true;

}

else if (isPrime(secondPart))

{

System.out.println("Goldbach's Conjecture is true “

+ "for “ + n + “ = “ + firstPart

+ “ + “ + secondPart);

done = true;

}

else

firstPart = primeAfter(firstPart);

}

}

In order to simplify the writing of the main method, we assumed the existence of the methods nextNumber and testGoldbach. Similarly, to simplify the writing of testGoldbach, we have assumed the existence of two other methods: isPrime that tests a number to see if it is prime and primeAfter that returns the next prime following a given value. We have asked you to supply a definition for the method isPrime in the exercises. The next example contains a definition of the method primeAfter.

Example 7

The method primeAfter shown here returns the next prime following its argument n. It assumes that n is a prime number. If n = 2, the next prime is 3 but otherwise n must be odd and only succeeding odd values are examined.

private static int primeAfter (int n)

{

int value;

if (n == 2)

value = 3;

else

{

value = n + 2;

while (!isPrime(value))

value += 2;

}

return value;

}

A solution should always be well-documented with comments to assist a reader. Comments for a program normally include a description of the purpose of the program, name(s) of the author(s), and the date. Instructors may require additional items such as the course name, your student number, the instructor's name, and so on. Comments for each method normally include a description of its purpose, notes on any parameters, and a description of the value returned (if any). In the next example, we have provided such documentation to an almost complete solution to our problem of testing Goldbach's Conjecture (lacking only the method isPrime that tests a number to see if it is prime). The style that we have used for comments is compatible with the style required by the Javadoc program discussed in Appendix F. Your instructor may suggest another style.

Example 7

The class GoldBach contains an almost complete solution to the problem posed at the start of this section: to attempt to verify Goldbach's Conjecture for values supplied by a user. One method has been left to be supplied by the reader.

/**

* This program repeatedly prompts a user for even integers

* greater than 2, forcing the user to supply valid values.

* The user can terminate the program by supplying a value of

* zero. For each valid input value, the program determines

* whether or not Goldbach's Conjecture holds for that value

* and prints an appropriate message.

* Goldbach's Conjecture states that any even integer greater

* than 2 can be written as the sum of two primes.

* @author Adrienne Geoffrey

* @version 1.0 July, 2002

*/

class Goldbach

{

/**

* Repeatedly get numbers and test each one to see

* if Goldbach's Conjecture is correct for that value.

* The sentinel value zero causes the program to stop.

*/

public static void main (String[] args)

{

int value = nextNumber();

while (value != 0)

{

testGoldbach(value);

value = nextNumber();

}

}

/**

* Prompt a user for a non-negative even integer other

* than 2, prompting repeatedly, if necessary, until a

* valid value is supplied.

*

* @return an int - either 0 or an even value> 2

*/

private static int nextNumber ()

{

int response;

do

{

System.out.println("Give an even integer> 2 “

+ "O to stop)");

response = In.getlnt();

}

while (response < 0 || response%2 != 0 || response 2) ;

return response;

}

/**

*Test Goldbach's Conjecture for a given integer and print

* an appropriate message based on the results of the test.

*

*@param n an integer assumed to be even and > 2

*/

private static void testGoldbach (int n)

{

int firstPart = 2;

boolean done = false;

while (! done)

{

int secondPart n - firstPart;

if (secondPart < firstPart)

{

System.out.println("Goldbach's Conjecture is "

+ "false - it fails for II + n);

done = true;

}

else if (isPrime(secondPart»

{

System.out.println("Goldbach's Conjecture is true”

+ "for " + n + " = " + firstPart

+ " + " + secondPart);

done = true;

}

else

firstPart primeAfter(firstPart);

}

}

private static boolean isPrime (int n)

{

// to come

}

/**

* Find next prime number (in increasing order) after n.

*

* @param n an integer assumed to be a prime number

* @return an int - the next prime after n

*/

private static int primeAfter (int n)

{

int value;

if (n = = 2)

value = 3;

else

{

value = n + 2;

while (!isPrime(value))

value += 2;

}

return value;

}

}

Exercises 5.7

l. Find two primes whose sum is equal to the given number.

(a) 4 (b) 28

(c) 38 (d) 54

2. Complete the definition of the method isPrime whose header is

private static boolean isPrime (int n)

The method should return the value true if and only if n is a prime number. You may assume that n > 1. Include comments in your definition.

3. In addition to the conjecture that we have been examining in this section, Goldbach also proposed that all odd integers greater than six could be written as the sum of three primes. This conjecture, like the one that we have studied, has not yet been proven or disproven. Write a program, similar to the one that we have developed, to test this conjecture.