Loops - Multimedia Introduction to Programming Using Java - page 247

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.

Optimization
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:

b&&(k!=p)
We can make another optimization. Suppose an integer d divides p. Then:

p=d*(p/d)
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.

7.4.4 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.

Activity
7-3.4

// 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