Java Reference
In-Depth Information
We have to: (1) make sure the invariant is true initially and (2) implement
the English statement “Process k ”.
1. The invariant is truthified using the assignment b= p > 1; —with k=2 ,
the range 2..k-1 is empty.
2. To process k means to add 1 to k if and only if k does not divide p.
To summarize, always increment k , and make b false if k divides p .
This gives us the algorithm of Fig. 7.4.
We can make an optimization. Once b becomes false , it remains false
because the only statement that changes b (after its initialization) is the statement
b= false ; . Therefore, it makes sense to terminate the loop if it is recognized that
b is false . We do this by changing the loop condition to:
We can make another optimization. Suppose an integer d divides p. Then:
One of d and p/d is at most sqrt(p) and the other is at least sqrt(p) .
Therefore, only the integers in the range 2..floor(sqrt(p)) have to be
checked to see whether they divide p . We leave it to you to change the algorithm
to take this into account. Make sure your algorithm evaluates sqrt(p) only once.
You will find the functions in class java.lang.Math helpful.
A schema for reading
Activity 7-3.4 develops a schema for reading a list of nonzero values from the
Java console and processing them. Activity 7-3.5 uses this schema to print the
sum of a sequence of nonzero values that are read from the Java console.
// Set b to "p is a prime "
b= p > 1;
int k= 2;
// { invariant: b==(p>1 and no integer in 2..k-1 divides p) }
while (k != p) {
if (p%k==0) {
b= false ;
k= k + 1;
// { b = (p > 1 and no integer in 2..p-1 divides p) }
Figure 7.4:
Testing primality
Search WWH ::

Custom Search